回顾：同态

根据对抽象代数的知识，同态的大体性质如下：
$$
E(a)\oplus E(b)=E(a+b)
$$

$$
E(a)\odot E(b)=E(a\cdot b)
$$

同态加密算法包括全同态（FHE）、部分同态（SWHE）和半同态（PHE）三种。

FHE：支持无限次的乘法和加法运算，但是复杂度高，实际应用较少。

SWHE：支持有限次的加法和乘法运算。

PHE：只支持加法或者乘法运算的一种，加法同态算法有Paillier算法、DGK算法、OU算法、基于格密码的方案等；乘法同态有RSA算法、ElGamal算法等。PHE实际应用较多。

Paillier算法

Paillier是一个支持加法同态的公钥密码系统。

密钥生成

随机选择两个大素数$p,q$，满足：
$$
\gcd(pq,(p-1)(q-1))=1
$$
计算$n=pq$和$\lambda=\mathrm{lcm}(p-1)(q-1)$。

随机选择整数$g\in Z^*_{n^2}$，或者直接令$g=n+1$，优化计算速度。

定义$L$函数：
$$
L(x)=\frac{x-1}n
$$
计算：
$$
\mu=(L(g^\lambda\bmod n^2))^{-1}\bmod n
$$
得到公钥$(n,g)$，私钥$(\lambda,\mu)$。

加密

给出明文$m$，满足$0\le m\le n$。

选择随机数$r\in Z^*_n$，满足$\gcd(r,n)=1$。

计算密文：
$$
c=g^mr^n\bmod n^2
$$
如果取得$g=n+1$，根据二项式定理：
$$
g^m=(n+1)^m=\dbinom m0n^m+\dbinom m1 n^{m-1}+\cdots+\dbinom m{m-2}n^2+mn+1\pmod {n^2}
$$
前面的$m-1$项全是$n^2$的倍数，模下消去了，简化为：
$$
g^m=mn+1\pmod {n^2}
$$

解密

给出密文$c$，满足$c\in Z^*_{n^2}$。

计算明文消息：
$$
m=L(c^\lambda\bmod {n^2})\mu\bmod n
$$

例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
import os


flag = b"NSSCTF{**********}"
p = getPrime(2048)
q = getPrime(2048)
n = p * q
g = n + 1
flag = flag + os.urandom(256)
m = bytes_to_long(flag)
assert m < n
c = (pow(g, p, n * n) * pow(m, n, n * n)) % (n * n)
print(f"c={str(c)}")
print(f"n={str(n)}")
print(f"hint={str(pow(m,n,n*n))}")


'''
c=225125450220105311041046087138705014935254833514432026429584708396889028070062588108440123503358315412941287776223277500809768767439104080138297877350350894870758555269962097045159281057417431708547199138245618813714897557577285863754036266189213471368988610466376049286399874738062055685783390740595224944655129698982615040363901449545718380849761071015663791441186331518855739660902574919658732296357516846617576532097729752124495525310383044246570860459909674468043892116366954178748744887759943538790955380359436920063097509390536113768584902582460152926841907280244934216418491322797359434627754957992373050770075511579834413910935998173887010591932095758778213506980556707387273313496684061141759069963822192246551429983980602784990878940678014896861847624508034734156619132941559616428732594747155812840073301505961649354821739626425210040140140650554613157261226142497098560014081654159162728304425366810991382925509980326196236887943866743844631440548314644099174455685333882262795291937108712195373810627256662737628113029324427725347874524870861726805090042722616988124350541708398849119521144223001484465059991547990967909997007025255966479981919446021970120511978531963304185576055142155556544534647723351656844147958836545604036280498193500867152760851781231961559038319804525142533245794507887086366035722991225921822049271508605775131456684268049567333571305767713317603509041456665383432380458303139215731899608675150974435258791424958521435089856187414088512969509730099511262804937577771637135080016736306516158564202320479634578997068609714361458607314838738852711267579801655606675023948561754394369562904377238896770861047226941797609026757220098060456408394694512893139400876964371093558705745860523407195806511035991545808668572847832037238730648633886746413394313505294649066849052224646247997606337262457830075157683947211444584365887544810340666518252333865602941279237496051328375479993587757115598218473119972573396768024836804836954132576124452286424703686303724425547789543965055806303501780543406870213426791296938778530045481070868000304044514218232380289752757390300367760650522841703714524787933373399597582884888995101012481882069017642507612679191655440043567769752947541659407893649684979816018588056421086155682587686444696839473117919463948740598839356581628532707900766874721178735996094304063716395016189050622613865084670796925930632957269961065884332253157016662708299839723103293775144413608290811536878360518365969977672
n=537704258136737772334289112157748201800577202045620524505164301000631802631518587884386010036030239953729672206334839422975257173569581511943218509199368473534767909131533916054000343397476255472410057803958031686283319265951508688824310413358459958769136535050441162363642859566835559964713658249715369502842906062505206255731671726850056726942898220380975891747284373542762467274135972474456753867954779496195382189948988745920240482811159002813575817211618052191504265204351143241124177136745488759794281466672726136044652606085144968587996290914257439088900301074791431625031800127807318907794431078348358129522553577048782080298489769456218151884724675077231784845616941801486600893202954039362083246165052316620134739383905800413890856823428743847766265894746887631528817253743766088118533423311798345443766948094538302985091421660682136033531115503987607110481356904149149526282183360828773159635634730439988764520577060231547737606453192992788155122703192824963856686478000004264736216604217895714882969433531376365800710689831597596633161940749894182066753234853099532538054185144292479569863660946353095969092374268598983684020415150102396846616294660770625160902861916257029081351903872365230567791249525163496231055895067
hint=47886103635974061334738696817505925206008923897565928150561771513914724526595573829591619709938559400940389141961851599955385265501826710621148821656831141085075562581864479233819131947415101078882068156163161848949521314963939166893511103952224692035005548780056277062017247931909057899253665428766657713029336880637928048151697855321187382076094403707286731411067921432004568329507804813975821978559221476933925854656445865719791207916111962826391396743644316463136438819988590704146950416860857554126676137265643589023911865407086113823589909768612304751490985778202249113266072429773376059806740293230440346878164196957488528640988752910108879722554389253825075538112288942832674983293521863664807642835037726668137699968092875962464625663543111536462033441813622214186431402007971410782513784521523246689064395099905282157694474068014013696412472311829756135290113812615257159471234175572894243757785555225944765219006077811656790178793248029858780954722807362472772119239096865144691982879763702595804240333195592747878503327699078886932376601205231739345645128969631502358729857038969868954692589495208914061479786322546773676859671126744502137589452004253647691303411052856915756464022560754512403296905511498273403466513184930519859058769900206628155880057348169594642309562380520586287635379283568522431874866504161213852947626202329695380933021696888632278381377801478650004662055042607980254914370975248463287962595759260914565488610311073394497076658915022604107825761748655952754203536242004955569468685796492106854447889421926172288692056518641428557695760344780401512911326772988689291340211959826809107210891399237585398110490266424018109890469033675344944316169138618595122787320628548024427684447970316867368904611136038590785545417930521148331279101090177401733386548020680836924024562578327764829143717197122938468927540011778852803272225391981411647224716134649523022711971744197814091168439648167266615972644774754582164498033839364474819015370267923120197091159805765686532165410857119247801897165746399333797829911056993706487584253035779480029520748480701096802590903142242892610898833928011746466021002547650026168978858744273473970883554693126359349655013051523511240984880443925387885665601883119494945669268976784670013509831304571675418774692098993256394139735277956696398163556362611953621069406975863327869760150215045731920838652536753008296599617886665590801532574846096634784646720344297528527329570379209738690849026495446253840
'''

发现：
$$
c=(g^p\bmod {n^2})(m^n\bmod n^2)\bmod n^2
$$

$$
h=m^n\bmod {n^2}
$$

这里的加密似乎和原加密算法里的有些出入，记为：
$$
c’=g^p=(n+1)^p=np+1\pmod {n^2}
$$
原加密式子可以转化为$c=h(np+1)\bmod {n^2}=hc’\bmod {n^2}$，得到：
$$
c’=np+1+kn^2
$$

$$
\frac {c’-1}n=p+kn=p(1+kq)
$$

发现公因子，可以提出来，得到$p$之后用$h$的式子求解RSA即可：

这里发现解密时由于模数为$n^2$、指数为$n$，所以求解欧拉函数的时候一定会发生模不互素，但是发现$n$是$4096$位的数，flag尽管做了一定的padding处理但是还是显得有些小，干脆直接在模$n$下进行计算即可，$n$和$(p-1)(q-1)$一定是不存在因子的：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2

c = 225125450220105311041046087138705014935254833514432026429584708396889028070062588108440123503358315412941287776223277500809768767439104080138297877350350894870758555269962097045159281057417431708547199138245618813714897557577285863754036266189213471368988610466376049286399874738062055685783390740595224944655129698982615040363901449545718380849761071015663791441186331518855739660902574919658732296357516846617576532097729752124495525310383044246570860459909674468043892116366954178748744887759943538790955380359436920063097509390536113768584902582460152926841907280244934216418491322797359434627754957992373050770075511579834413910935998173887010591932095758778213506980556707387273313496684061141759069963822192246551429983980602784990878940678014896861847624508034734156619132941559616428732594747155812840073301505961649354821739626425210040140140650554613157261226142497098560014081654159162728304425366810991382925509980326196236887943866743844631440548314644099174455685333882262795291937108712195373810627256662737628113029324427725347874524870861726805090042722616988124350541708398849119521144223001484465059991547990967909997007025255966479981919446021970120511978531963304185576055142155556544534647723351656844147958836545604036280498193500867152760851781231961559038319804525142533245794507887086366035722991225921822049271508605775131456684268049567333571305767713317603509041456665383432380458303139215731899608675150974435258791424958521435089856187414088512969509730099511262804937577771637135080016736306516158564202320479634578997068609714361458607314838738852711267579801655606675023948561754394369562904377238896770861047226941797609026757220098060456408394694512893139400876964371093558705745860523407195806511035991545808668572847832037238730648633886746413394313505294649066849052224646247997606337262457830075157683947211444584365887544810340666518252333865602941279237496051328375479993587757115598218473119972573396768024836804836954132576124452286424703686303724425547789543965055806303501780543406870213426791296938778530045481070868000304044514218232380289752757390300367760650522841703714524787933373399597582884888995101012481882069017642507612679191655440043567769752947541659407893649684979816018588056421086155682587686444696839473117919463948740598839356581628532707900766874721178735996094304063716395016189050622613865084670796925930632957269961065884332253157016662708299839723103293775144413608290811536878360518365969977672
n = 537704258136737772334289112157748201800577202045620524505164301000631802631518587884386010036030239953729672206334839422975257173569581511943218509199368473534767909131533916054000343397476255472410057803958031686283319265951508688824310413358459958769136535050441162363642859566835559964713658249715369502842906062505206255731671726850056726942898220380975891747284373542762467274135972474456753867954779496195382189948988745920240482811159002813575817211618052191504265204351143241124177136745488759794281466672726136044652606085144968587996290914257439088900301074791431625031800127807318907794431078348358129522553577048782080298489769456218151884724675077231784845616941801486600893202954039362083246165052316620134739383905800413890856823428743847766265894746887631528817253743766088118533423311798345443766948094538302985091421660682136033531115503987607110481356904149149526282183360828773159635634730439988764520577060231547737606453192992788155122703192824963856686478000004264736216604217895714882969433531376365800710689831597596633161940749894182066753234853099532538054185144292479569863660946353095969092374268598983684020415150102396846616294660770625160902861916257029081351903872365230567791249525163496231055895067
hint = 47886103635974061334738696817505925206008923897565928150561771513914724526595573829591619709938559400940389141961851599955385265501826710621148821656831141085075562581864479233819131947415101078882068156163161848949521314963939166893511103952224692035005548780056277062017247931909057899253665428766657713029336880637928048151697855321187382076094403707286731411067921432004568329507804813975821978559221476933925854656445865719791207916111962826391396743644316463136438819988590704146950416860857554126676137265643589023911865407086113823589909768612304751490985778202249113266072429773376059806740293230440346878164196957488528640988752910108879722554389253825075538112288942832674983293521863664807642835037726668137699968092875962464625663543111536462033441813622214186431402007971410782513784521523246689064395099905282157694474068014013696412472311829756135290113812615257159471234175572894243757785555225944765219006077811656790178793248029858780954722807362472772119239096865144691982879763702595804240333195592747878503327699078886932376601205231739345645128969631502358729857038969868954692589495208914061479786322546773676859671126744502137589452004253647691303411052856915756464022560754512403296905511498273403466513184930519859058769900206628155880057348169594642309562380520586287635379283568522431874866504161213852947626202329695380933021696888632278381377801478650004662055042607980254914370975248463287962595759260914565488610311073394497076658915022604107825761748655952754203536242004955569468685796492106854447889421926172288692056518641428557695760344780401512911326772988689291340211959826809107210891399237585398110490266424018109890469033675344944316169138618595122787320628548024427684447970316867368904611136038590785545417930521148331279101090177401733386548020680836924024562578327764829143717197122938468927540011778852803272225391981411647224716134649523022711971744197814091168439648167266615972644774754582164498033839364474819015370267923120197091159805765686532165410857119247801897165746399333797829911056993706487584253035779480029520748480701096802590903142242892610898833928011746466021002547650026168978858744273473970883554693126359349655013051523511240984880443925387885665601883119494945669268976784670013509831304571675418774692098993256394139735277956696398163556362611953621069406975863327869760150215045731920838652536753008296599617886665590801532574846096634784646720344297528527329570379209738690849026495446253840

c1 = c * gmpy2.invert(hint, n**2) % n**2
p = gmpy2.gcd((c1 - 1) // n, n)
q = n // p
phi = (p - 1) * (q - 1)
d = gmpy2.invert(n, phi)
print(long_to_bytes(pow(c, d, n)))