EDI
JOIN US ▶▶▶
招新
EDI安全的CTF战队经常参与各大CTF比赛，了解CTF赛事。
欢迎各位师傅加入EDI，大家一起打CTF，一起进步。（诚招web re crypto pwn misc方向的师傅）有意向的师傅请联系邮箱root@edisec.net、shiyi@edisec.net（带上自己的简历，简历内容包括但不限于就读学校、个人ID、擅长技术方向、历史参与比赛成绩等等。
点击蓝字 · 关注我们
01
出题脚本
import libnumimport gmpy2#生成素数p=libnum.generate_prime(1024)q=libnum.generate_prime(1024)e1 = 2333e2 = 23333m = "flag{welc0me_t0_crypt0}"m = libnum.s2n(m)n= p * qc1 = pow(m,e1,n)c2 = pow(m,e2,n)print("n1=",n)print("e1=",e1)print("c1=",c1)print("n2=",n)print("e2=",e2)print("c2=",c2)'''n1=23238670943636821229418198303696484033546548725320789511905184154464216574741336420462113476232743317674222866751093726563927046479777004335916662385654363671981145970838481780467314122689318197765541339080943964401712288019261997278880569305609867072995156369970541326917806924828266252671593995048442532205000173808327324689004622910138972973020843899799630065127128795837581940656761058942402129287237418602146259535849773033547897644971570907544154492928994390326181040514114380840249880096266213247968909582481332519488661154930387966387826269395430760825138626867484931995579577138860619071549478038088017447009e1= 2333c1=18249951123827936165110580108626580495569983472886252647548920954813743888852830151046170017781231091700033184374232735767659267152993780655419031788064573074432852737421170018695091508312613791712968569426044446003893524499993942469924055917610581437934018395205923365722308058060701753550002687559753741722897439261112014646640265259851687938415829398941891711287915322950631515969769297488553388051195049498888355788449766954664309328459158523026284222387138684777317017359506335617816824881215515925834000930019719101527540325546051341545248004838527948992446199245815116677460777863756165903160043717884206023382n2=23238670943636821229418198303696484033546548725320789511905184154464216574741336420462113476232743317674222866751093726563927046479777004335916662385654363671981145970838481780467314122689318197765541339080943964401712288019261997278880569305609867072995156369970541326917806924828266252671593995048442532205000173808327324689004622910138972973020843899799630065127128795837581940656761058942402129287237418602146259535849773033547897644971570907544154492928994390326181040514114380840249880096266213247968909582481332519488661154930387966387826269395430760825138626867484931995579577138860619071549478038088017447009e2= 23333c2=7955139316265403454410869324559086679792452291082478294938626696455440501518770720890618924710600618728892805002826291554309528242718556778799220934997957252598156522651316071568577717103484365761675994644581686874447318802052597167355210271850694833930087720693601093890291367111342951748574782783379972400122991612273780929274153328356249253755599248624362221804698229077222704278437620509108405366407139846060428874464492713448458808410966953409339598399382157276997804601283687609116366581560012242328589201364644291178965281042641498514398352040978473264401945435776065752240522273857215764354822976705881386403'''
02
攻击原理
1、攻击条件：
相同的模数：多个明文使用了相同的模数进行加密
不同的指数：每个明文都有不同的公钥指数e
2、相同的模数
密文c1、c2都公用一个模数n。
c1 = pow(m,e1,n)c2 = pow(m,e2,n)
3、不同的指数
= 2333= 23333
4、共模方式加密的同余式
5、攻击思路：我们的思路是求出明文m，所以要想办法把明文m的指数给去掉
6、根据裴蜀定理，如果两个数互质(最大公因数为1)，那么它可以表示为：
7、那么这里我们可以将指数e1,e2代入式子中
注意这个前提：gcd(e1,e2) = 1，我们知道e1=233,e2 = 23333，所以可以适用此定理。
8、现在我们将两个方程式结合起来看：这里如果可以让和分别乘上和那么就可以抵消掉的指数 即因为可以得到
9、根据同余式相乘的性质：
10、所以这里有：将这两个式子分别乘上和的次方
11、根据同余式相乘的性质：
12、所以这里有：
13、所以我们知道了，求解明文的方程为：
14、x、y的结果肯定是一正一负，所以要判断一下x、y的值如果为负数就要进行模逆运算。
03
解题脚本
n =23238670943636821229418198303696484033546548725320789511905184154464216574741336420462113476232743317674222866751093726563927046479777004335916662385654363671981145970838481780467314122689318197765541339080943964401712288019261997278880569305609867072995156369970541326917806924828266252671593995048442532205000173808327324689004622910138972973020843899799630065127128795837581940656761058942402129287237418602146259535849773033547897644971570907544154492928994390326181040514114380840249880096266213247968909582481332519488661154930387966387826269395430760825138626867484931995579577138860619071549478038088017447009e1 = 2333e2 = 23333c1 =18249951123827936165110580108626580495569983472886252647548920954813743888852830151046170017781231091700033184374232735767659267152993780655419031788064573074432852737421170018695091508312613791712968569426044446003893524499993942469924055917610581437934018395205923365722308058060701753550002687559753741722897439261112014646640265259851687938415829398941891711287915322950631515969769297488553388051195049498888355788449766954664309328459158523026284222387138684777317017359506335617816824881215515925834000930019719101527540325546051341545248004838527948992446199245815116677460777863756165903160043717884206023382c2 =7955139316265403454410869324559086679792452291082478294938626696455440501518770720890618924710600618728892805002826291554309528242718556778799220934997957252598156522651316071568577717103484365761675994644581686874447318802052597167355210271850694833930087720693601093890291367111342951748574782783379972400122991612273780929274153328356249253755599248624362221804698229077222704278437620509108405366407139846060428874464492713448458808410966953409339598399382157276997804601283687609116366581560012242328589201364644291178965281042641498514398352040978473264401945435776065752240522273857215764354822976705881386403# e1,e2必须互质,即最大公因数必须是1if libnum.gcd(e1,e2) != 1:gcd(e1,e2) != 1")exit(0)# 使用扩展欧几里得求出x,y的值_ , x ,y=gmpy2.gcdext(e1,e2)if x < 0:c1 = libnum.invmod(c1,n)x = abs(x)if y < 0:c2 = libnum.invmod(c2,n)y = abs(y)m = (pow(c1,x,n) * pow(c2,y,n)) % n# flag{welc0me_t0_crypt0}print(long_to_bytes(m).decode())
EDI安全
扫二维码｜关注我们
一个专注渗透实战经验分享的公众号
原文始发于微信公众号（EDI安全）：RSA共模攻击 by shenqi
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论