Automne's Shadow.

Paillier Cryptosystem对应的问题解析

sage Paillier Cryptosystem
2020/06/11 Share

Crypto

是的，我还在

automne

2020年太难了。

Paillier Cryptosystem是一种1999年发明的公钥密码系统，具体的理论细节可以直接看下面的链接：

https://www.anquanke.com/post/id/204720#h2-0

直接看一道CTF题，题目源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from Crypto.Util.number import GCD
from Crypto.Util.number import bytes_to_long
from Crypto.Util.number import getRandomRange

from util import GeneratePrimePairByBitLength
from FLAG import flag

def Encrypt(m, N):
    assert 0 <= m < N

    r = getRandomRange(1, N)
    while GCD(r, N) != 1:
        r = getRandomRange(1, N)

    x = pow(1 + N, m, N * N)
    y = pow(r, N, N * N)
    return (x * y) % (N * N)

p, q = GeneratePrimePairByBitLength(1024, 2 ** 512)
assert p.bit_length() == q.bit_length() == 1024

N = p * q
m = bytes_to_long(flag)
c = Encrypt(m, N)

print (c, N)

给出的output是密文c和模数N

1
(42819441760414983635212613714604410555443270405423002502827818537215418237802946896614555651891651815808758847477066571078094368125288370720892300699618974545413074742004427136423203668783124078723589527158112850809662287227621967047290073015944400358832410703410040546249151485394106326351505517997088272146467836125931711219802860863944959027119163278330888013058663244952951387446438734970998972561539994686828786764154172546497122853547807718724403912037517035681677527056095023379015179868865500086749889311482040527782181364565565852026863579935692210566880088717382987456738065898455637831988456373514400957171013708931415730408959984904521274799417834385576235516025501188338066442510344117771403769612268044703079615539605495683636094118658539752377669879428314549945797573770721884651513123702255579611168522274314428183676574059145665721183529135161513026304652580400063409784411128187563324940449092904404692234543756523527181141144524382403448227267313964407771720228184842413196572317432680657482129021092704696431286665506988605115737233709374645128585825951818299155523259368236801764569657102640471777825044151930348301976000317148299239711617937598416895434192161468250193944563523571929807087856692478569468731698L, 16370355290960753791969092003628967743476951579599723812106056192971165318521694274626292473435023374651127436836528800141310198349143414917500115710190867714535122604090379875693049199978868681491026810827425773654015666550626753844746457863599458429598064634528269304989675902232674657888124943049085066904024625754901915605096602355263612943520612809340443352229041355337934913704555256791448788109553320750045678851200272506735292835746406097389635570017013247093236229385102657335436092732405644778928244291608536597046768950979757322801247936577720853861146162290582371111285843463755876559676345045797259298949L)

首先是尝试分解N，使用yafu，成功分解，分解的p，q后面会用到。

automne

从源码里可以看到，主要的未知数是生成的随机数r和要求解的flag明文m

求r、x、y

y = pow(r,N,N*N)

从这个WP得到了启发

https://ctftime.org/writeup/12399

简而言之：

c=(rN∗(1+N)m)mod(N∗N)c = (r^N * (1+N)^m) mod (N*N)

推导出：

cmodN=rNmodNc mod N = r^N mod N

然后就是求解r的过程

上面的式子可以这样理解：

当m=1,(1+N)1当m=1, (1+N)^1

当m=2，(1+N)2=1+2N+N2当m=2，(1+N)^2 = 1+2N+N^2

当m=3,(1+N)3=1+3N+3N2+N3当m=3,(1+N)^3=1+3N+3N^2+N^3

……

所以才会有

cmodN=rNmodNc mod N = r^N mod N

这个式子，而这个式子里只有r一个未知数，这里的求解类似于RSA里求明文的过程。

c=memodNc= m^e mod N

所以首先要求出一个”私钥”

d=inverse(e,phi)=inverse(N,phi)d = inverse(e,phi) = inverse(N,phi)

phi=(p−1)(q−1)phi = (p-1)(q-1)

r=cdmodNr = c^d mod N

综上，就有了下面的sage代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#coding=utf-8

c = 42819441760414983635212613714604410555443270405423002502827818537215418237802946896614555651891651815808758847477066571078094368125288370720892300699618974545413074742004427136423203668783124078723589527158112850809662287227621967047290073015944400358832410703410040546249151485394106326351505517997088272146467836125931711219802860863944959027119163278330888013058663244952951387446438734970998972561539994686828786764154172546497122853547807718724403912037517035681677527056095023379015179868865500086749889311482040527782181364565565852026863579935692210566880088717382987456738065898455637831988456373514400957171013708931415730408959984904521274799417834385576235516025501188338066442510344117771403769612268044703079615539605495683636094118658539752377669879428314549945797573770721884651513123702255579611168522274314428183676574059145665721183529135161513026304652580400063409784411128187563324940449092904404692234543756523527181141144524382403448227267313964407771720228184842413196572317432680657482129021092704696431286665506988605115737233709374645128585825951818299155523259368236801764569657102640471777825044151930348301976000317148299239711617937598416895434192161468250193944563523571929807087856692478569468731698L

N = 16370355290960753791969092003628967743476951579599723812106056192971165318521694274626292473435023374651127436836528800141310198349143414917500115710190867714535122604090379875693049199978868681491026810827425773654015666550626753844746457863599458429598064634528269304989675902232674657888124943049085066904024625754901915605096602355263612943520612809340443352229041355337934913704555256791448788109553320750045678851200272506735292835746406097389635570017013247093236229385102657335436092732405644778928244291608536597046768950979757322801247936577720853861146162290582371111285843463755876559676345045797259298949

p = 127946689253613568412267588733089588878698870673566029155443041646015385234270946929380693485004666985498835446037309569712522008317174096875032285031809584544876770989737477334159034091139494237957941608700903886157775389085119856310343643663752808174240070057591043681127647318721621374071455898248230802847
q = 127946689253613568412267588733089588878698870673566029155443041646015385234270946929380693485004666985498835446037309569712522008317174096875032285031809583732150881634200106643504157768601581455155657620419182150455519905535646868745973981243334302232249794619537609572630891723667980911713519480805025400667

c2 = pow(c,1,N)
N2 = N*N

phi = (p-1)*(q-1) 
d =  inverse_mod(N,phi)

r = pow(c2,d,N)
print r
r = long(r)

y = pow(r,N,N2)
print y

c3 = pow(c,1,N2)

x = c3//y
print x

结果如下，这里需要注意的是需要把解出来的r变成long型，否则求出的x和y是错误的：

1
2
3
4
5
6
r=
6481761966406294982533515162746605080221837193307234121868100978056065209261096880613478819237675638807253346122923266106789898815063823372575317529206991789363635749130750935587113232956825154874103820595668014233754081113966321344281090524062525662262529634709335186589478206925488270424349976586230752149237097315697770891101470641340257873527984498552648227024629699031840392010363359708655918576739411832692105576189494296941488113028040749712720499467126865531203323658306164426794072183413065688036470219816411122823379041218615260137566893798107965640782520126591119611121687826282479972660228343251853134531
y=
92466823498474601490830036476978179305475497371670777059045707452479662971748745098559176980151104999260558363331349821649619591269676313113634760912842426945963277445024893916575823362754487092663763806024498226325871908142929814718643966754178785369816506653078866510648491689036832364710317414516539575204954377070549332329225512212982320454489690356533327595241722425936656604109477382975386893237684690458745864381940213468624851201768030448436323363365147043464667772837294674132608783313272359754558214868515965876533541818233815250302737633259325437410281162225486321606160966434029756233239714431041765226338313315144554735937656542985740332650671048736065665150521981330522026583790422362969198107686524181615125493687558915726717684352633866904851128995417545517072358220653766300040170699774947385505214305949623031694041057787218792048993582486632992090118965160285743561545003993682923318993025165745906561067145205810129188173973828018934413676085264987996054649195118729607330245145949648335919931739467845124773918310169173929915543104351036237478106216560712598742057494362430347967758197337349634886881313896642317071224948326171444364893429909743912603796685407029261656876609498259961790639010962999501592099126
x=
4760529069427176311258577231723014060713459430859271397382240049677270349380348945016663676817345822428840603371464574739303741188713279062811040534490749897761417363984846093341095236476833081902858001396998933292379753509995729861853532031458898184235701357504817048159147661863828095779779779076009554542992841810938597251528715107578511718921120417783514652569590541865662591716698928664620204865146964711735077795953880101290854039714347083707543140831442477619569533116108530986278514978048829954403666883997926594603161062768219730004531516173633860354027544767277835002453147874898372232231584670609747734041322914388840185467750943544104358345774349689586683542234093107232016290204396845151284010235684484550471471063580232463178275178530290

求m

x = pow(1 + N, m, N * N)

搜索DLP相关的解题方法，直到找到这篇题解：

https://github.com/ashutosh1206/Crypto-CTF-Writeups/tree/master/2017/ASIS-CTF-Quals/DLP

automne

上图的解释已经非常清楚了

上图的enc对应上一节解出来的x，直接在sage里搞起

automne

转成字节，flag到手：

automne

原文作者: Automne

原文链接: https://ce-automne.github.io/2020/06/11/Paillier-Cryptosystem对应的问题解析/

发表日期: June 11th 2020, 8:29:00 pm

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 求r、x、y
  2. 2. 求m
Total : 62
2021
2020
2019
2018
2017
lfsr z3 python reverse fat git broadcastreceiver sha-1 cbc sqli sqlite golang race condition luks hashcat photorec MAC sso oauth 2.0 padding oracle csp xss abe vdex ransomware frida ndk pwntools hashpumpy sourceleakhacker ecb socat fastjson JdbcRowsetImpl idea servlet volatility inet_aton boneh durfee lcg rabin egcd cipolla's algorithm spi snakeyaml ScriptEngineManager malware codereflect mysql yara plugin deserialization log4j rsa binary javascript prototype pollution nodejs shiro ysoserial primefac rsatool ssl AES tshark gmpy2 RsaCtfTool Hex flask ssti ecc Modular operation WebGoat8 order by tomcat nim game .iso gpg outguess sage google cloud sdk zsteg base58 fermat multi-primes prng rmi jndi Paillier Cryptosystem rsa lsb oracle SQL Injection ping delay xor CAS 单点登录 渗透测试 weblogic xxe reflect 010 editor gcd
Crypto Android Web Forensics Misc