密码CTF（4)——e和phi不互素

参考

RSA中e和phi不互素

AMM算法

AMM算法简要理解

RSA系列解题研究——e与phi不互素 - 先知社区 (aliyun.com)

e与phi不互素 --- 四 + 1 + 1 + 1道题详记-CSDN博客

总述

• gcd(e,φ(n))比较小时可以考虑iroot直接开根，当直接开根跑不出来时，考虑有限域内开方
• gcd(e,φ(n))很大时，考虑AMM算法或有限域开方
• 总之，大多数都可以使用有限域开方解题；但是e与（p-1）互素时，模p比较简单，而且可以是多因子（phi中互素的因子都参与，例五）

一、[LitCTF 2023]e的学问

_gcd=gcd(e,phi)=2比较小，直接iroot开e//_gcd次根

1.题目：

# from Crypto.Util.number import *
# m=bytes_to_long(b'xxxxxx')
# p=getPrime(256)
# q=getPrime(256)
# e=74
# n=p*q
# c=pow(m,e,n)
# print("p=",p)
# print("q=",q)
# print("c=",c)
 
 
p = 86053582917386343422567174764040471033234388106968488834872953625339458483149
q = 72031998384560188060716696553519973198388628004850270102102972862328770104493
c = 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123

2.

import gmpy2
import libnum
 
e = 74
p = 86053582917386343422567174764040471033234388106968488834872953625339458483149
q = 72031998384560188060716696553519973198388628004850270102102972862328770104493
c = 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123
n = p*q
 
# 当e约去公约数后与phi互素
def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    t = gmpy2.gcd(e, phi)
    print(t)
    d = gmpy2.invert(e // t, phi)
    m = pow(c, d, n)
    print(m)
    msg = gmpy2.iroot(m, t)
    print(msg)
    if msg[1]:
        print(libnum.n2s(int(msg[0])))
 
decrypt(p, q, e, c)

LitCTF{e_1s_n0t_@_Prime}

二、[2023MoeCTF] bad_E

e和φ(n)不互素，但是e和p−1或者q−1互素，转化到模p 或者模q 下求解

m = c ^ d mod n
==>
m = c ^ d mod p
m = c ^ d mod q
(注：此推论满足的前提是------在c不是p或q的倍数，以及d是正整数的情况下，m = c ^ d modp 和m = c ^ d mod q 总是成立的，有兴趣的同志们可以自行查找推导过程，这里就不过多说了)

1.题目：

from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
e = 65537
 
print(p) 
# 6853495238262155391975011057929314523706159020478084061020122347902601182448091015650787022962180599741651597328364289413042032923330906135304995252477571
print(q) 
# 11727544912613560398705401423145382428897876620077115390278679983274961030035884083100580422155496261311510530671232666801444557695190734596546855494472819
 
with open("flag.txt","r") as fs:
    flag = fs.read().strip()
 
m = bytes_to_long(flag.encode())
c = pow(m,e,p*q)
print(c) 
# 63388263723813143290256836284084914544524440253054612802424934400854921660916379284754467427040180660945667733359330988361620691457570947823206385692232584893511398038141442606303536260023122774682805630913037113541880875125504376791939861734613177272270414287306054553288162010873808058776206524782351475805

2.解题：

_gcd=gcd(e,phi)= 65537，比较大，可以使用AMM算法。又因为e和q-1互素，所以可以将模n转换为模q.

3.将模n转换为模q---python脚本

import gmpy2
import libnum
 
 
p=6853495238262155391975011057929314523706159020478084061020122347902601182448091015650787022962180599741651597328364289413042032923330906135304995252477571
q=11727544912613560398705401423145382428897876620077115390278679983274961030035884083100580422155496261311510530671232666801444557695190734596546855494472819
e=65537
c = 63388263723813143290256836284084914544524440253054612802424934400854921660916379284754467427040180660945667733359330988361620691457570947823206385692232584893511398038141442606303536260023122774682805630913037113541880875125504376791939861734613177272270414287306054553288162010873808058776206524782351475805
n = p*q
# t = gmpy2.gcd(e, (p-1)*(q-1))
# print(t)  # 65537
gcd_q = gmpy2.gcd(e,q-1)  # 1
d = gmpy2.invert(e, q-1)
m = pow(c, d, q)
print(libnum.n2s(int(m)))

moectf{N0w_Y0U_hAve_kN0w_h0w_rsA_w0rks!_f!lP0iYlJf!M3ru}

三、[2023 一带一路金砖国家] crypto1

gcd(e,phi)=16也比较小，但尝试iroot开根跑不出来，这时考虑有限域内开方来求解.

1.题目：

from Crypto.Util.number import *
from flag import flag
import gmpy2
assert(len(flag)==38)
flag = bytes_to_long(flag)
 
p = getPrime(512)
q = getPrime(512)
 
e = 304
enc = pow(flag,e,p*q)
print(p)
print(q)
print(enc)
#9794998439882070838464987778400633526071369507639213778760131552998185895297188941828281554258704149333679257014558677504899624597863467726403690826271979
#10684338300287479543408040458978465940026825189952497034380241358187629934633982402116457227553161613428839906159238238486780629366907463456434647021345729
#88310577537712396844221012233266891147970635383301697208951868705047581001657402229066444746440502616020663700100248617117426072580419555633169418185262898647471677640199331807653373089977785816106098591077542771088672088382667974425747852317932746201547664979549641193108900510265622890793400796486146522028

2.

先分别求在模p和模q情况下的根，

R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()
print('res1 =',res1)
​
R.<x> = Zmod(q)[]
f = x ^ e - c
f = f.monic()
res2 = f.roots()
print('res2 = ',res2)
 
'''
这段代码是在Sage数学软件中运行的，用于求解一个在模质数p意义下的方程x^e=c的解。
代码定义了一个多项式环R，请注意 R. = Zmod(p)[] 这一句。这里 R 表示多项式环的名称， 表示所定义的环中的变量名是x，而 Zmod(p)[] 表示在模p的意义下定义了一个多项式。其中每个多项式的系数都是p的倍数，以确保在模p的意义下进行运算时不会出现浮点运算精度的问题。
接下来，代码定义了一个多项式 f = x^e - c。变量c和e在代码中的定义可能来自其他地方。通过将这个方程的领导系数归一化，再去除它，这个多项式被调整为monic的形式，并被保存在变量f中，以便计算方程的根。
接下来，代码再次调用了多项式 f 的roots() 方法，这一次将得到方程的一个根的列表。具体地，最终生成的变量res1是多项式f在模p意义下的根列表。注意，如果方程没有解，则res1变量将为空列表。
'''

再使用中国剩余定理

import libnum
 
 
res1 = [(9794998439882070838464987778400633526071369507639213778760131539958181412476665109234912082861186315555182138835423582044838702540615722254589975405417838, 1), (13040004482820523832593369471397517833778497118179135095460060922057247745471813715420854141, 1)]
p = 9794998439882070838464987778400633526071369507639213778760131552998185895297188941828281554258704149333679257014558677504899624597863467726403690826271979
q = 10684338300287479543408040458978465940026825189952497034380241358187629934633982402116457227553161613428839906159238238486780629366907463456434647021345729
c = 88310577537712396844221012233266891147970635383301697208951868705047581001657402229066444746440502616020663700100248617117426072580419555633169418185262898647471677640199331807653373089977785816106098591077542771088672088382667974425747852317932746201547664979549641193108900510265622890793400796486146522028
e = 304
res2 =  [(10684338300287479543408040458978465940026825189952497034380241345147625451813458569523087756155643779650342787980103143026719707309659717984620931600491588, 1), (10546228809984142588932616342715328321552379476608001942565701452107946512829920974970543251035295344551528300355346723241264610890289579898347512710457224, 1), (10482040874725218211680697533029686266663549008178103903160375044524596930137226728570965814342405902744600364128887860053217649327227406691784556292324776, 1), (7587150706925009448044848323078167245760828328035695310011484658921549852303397675427817183860064727119368187862675977689355242244610233605342877416416257, 1), (6929915755647234327756166117496179990985501469267159525699449630122977778850898949385810639276049628950031772419336027356980765474388162378519914225520495, 1), (6808250530139244545123813990883203034597988957283224721311935428815631349687956574294930913574694204299623102994534099823502106840178340882372782485458364, 1), (6614395009687937241208994970395255429016903307868654920376515166865642182499067352283924772101088740354565996920188686016365538542794213665633197273513278, 1), (6614140685746605896932899060022876834549907373367709600424726351002948121988351363544709782701044263811762583407690877268515310249161373039675771252203648, 1), (4070197614540873646475141398955589105476917816584787433955515007184681812645631038571747444852117349617077322751547361218265319117746090416758875769142081, 1), (4069943290599542302199045488583210511009921882083842114003726191321987752134915049832532455452072873074273909239049552470415090824113249790801449747832451, 1), (3876087770148234998284226468095262905428836232669272313068305929371998584946025827821526313978467409129216803164704138663278522526729122574061864535887365, 1), (3754422544640245215651874341482285949041323720685337508680791728064652155783083452730646588277111984478808133739902211129799863892519301077914732795825234, 1), (3097187593362470095363192135900298694265996861916801724368756699266080082330584726688640043693096886309471718296562260797425387122297229851091769604929472, 1), (202297425562261331727342925948779673363276181774393131219866313663033004496755673545491413210755710684239542030350378433562980039680056764650090729020953, 1), (138109490303336954475424116263137618474445713344495091814539906079683421804061427145913976517866268877311605803891515245516018476617883558087134310888505, 1), (13040004482820523832593369471397517833778497118179135095460060922057247745471813715420854141, 1)]
for i in res1:
    for j in res2:
        # 中国剩余定理
        m = libnum.solve_crt([int(i[0]), int(j[0])], [p, q])  # c3=libnum.solve_crt([c1,c2], [q1,q2])
        flag = libnum.n2s(int(m))
        if flag.startswith(b'flag'):
            print(flag)

b'flag{947b6543117e32730a93d1b43c98bc57}'

四、[0ctf 2016]RSA

1.题目：

c = 2485360255306619684345131431867350432205477625621366642887752720125176463993839766742234027524
n = 0x2CAA9C09DC1061E507E5B7F39DDE3455FCFE127A2C69B621C83FD9D3D3EAA3AAC42147CD7188C53
e = 3

2.解题：

分解n，得到：

p = 26440615366395242196516853423447
q = 27038194053540661979045656526063
r = 32581479300404876772405716877547

• 发现 gcd(e, p-1) = gcd(e, r-1) = e = 3, gcd(e, q-1) = 1

  但用
  e*d = 1 mod (q-1)
  m = c ^ d mod q
  求不出m

所以这里为什么求不出m，而题一可以求出m ?
因为m与p或q大小比较的问题，题一中p为512bits，明显比flag大，用p便可单独出来，而这题q明显比flag小，故求不出也在情理之中了

3.

import gmpy2
from Crypto.Util.number import *
import libnum
e = 3
c = 2485360255306619684345131431867350432205477625621366642887752720125176463993839766742234027524
n = 23292710978670380403641273270002884747060006568046290011918413375473934024039715180540887338067
 
p = 26440615366395242196516853423447
q = 27038194053540661979045656526063
r = 32581479300404876772405716877547
 
'''
sage:
R. = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()
R. = Zmod(q)[]
f = x ^ e - c
f = f.monic()
res2 = f.roots()
R. = Zmod(r)[]
f = x ^ e - c
f = f.monic()
res3 = f.roots()
print('res1 =',res1)
print('res2 =',res2)
print('res3 =',res3)
'''
 
res1 = [(13374868592866626517389128266735, 1), (7379361747422713811654086477766, 1), (5686385026105901867473638678946, 1)]
res2 = [(19616973567618515464515107624812, 1)]
res3 = [(13404203109409336045283549715377, 1), (13028011585706956936052628027629, 1), (6149264605288583791069539134541, 1)]
for i in res1:
    for j in res2:
        for k in res3:
            m = libnum.solve_crt([int(i[0]),int(j[0]),int(k[0])],[p,q,r])
            flag = libnum.n2s(int(m))
            print(flag)

 0ctf{HahA!Thi5_1s_n0T_rSa~}

五、[第三届江西省网络安全大赛]factor

1.题目：

n = 3454083680130687060405946528826790951695785465926614724373
e = 3
c = 1347530713288996422676156069761604101177635382955634367208

2.解题：

对n进行分解

p=11761833764528579549 
q=17100682436035561357 
r=17172929050033177661 

先考虑是多因子，但是在求逆元的时候发现没有逆元，所以猜测e与phi不互素

然后求e分别与p-1，q-1，r-1的最大公约数，发现e与p-1和r-1互素，所以

n = p*r
phi = (p-1)*(r-1)

3.

import gmpy2
import libnum
 
n = 3454083680130687060405946528826790951695785465926614724373
e = 3
c = 1347530713288996422676156069761604101177635382955634367208
p = 11761833764528579549 # 1
q = 17100682436035561357 # 3
r = 17172929050033177661 # 1
 
# phi = (p-1)*(q-1)*(r-1)
# d = gmpy2.invert(e, phi)   #  发现不互素
 
print(gmpy2.gcd(e, p-1))
print(gmpy2.gcd(e, q-1)) # 3
print(gmpy2.gcd(e, r-1))
d = gmpy2.invert(e, (p-1)*(r-1))
m = pow(c, d, p * r)
print(libnum.n2s(int(m)))

CMISCCTF{3_RSA}