rabbin的加密算法很简单，是rsa的衍生算法，区别在于rabbin算法的公钥是2
解密算法与常规rsa有点不同
在rsa算法中
p为任意素数
q为任意素数
phi=(p-1)*(q-1)
而p-1和q-1都是偶数，所以相乘是偶数，即2的倍数，此时利用e的模逆求d是不现实的，只能直接对c进行有限域n下的开平方运算
但n不是个素数，很难找到它的平方剩余
于是我们把式子分解一下
c
≡
m
2
(
m
o
d
n
)
分
解
为
c
≡
m
2
(
m
o
d
p
)
c
≡
m
2
(
m
o
d
q
)
cequiv m^2~(mod~n)newline分解为newline cequiv m^2~(mod~p)newline cequiv m^2~(mod~q)
c≡m2 (mod n)分解为c≡m2 (mod p)c≡m2 (mod q)
找到域p和q上的解m，
我自己生成并复现了一个，具体原理是找到域p和q上的平方根mp和mq，再通过CRT（孙子定理）找到通解
解密需要知道p和q，本质上来讲不算是攻击
参照 ctf wiki 提供的解题思路：
import gmpy2
from QR import Tonelli
from Crypto.Util.number import *
def Tonelli(a,p):
def legendre(a, p):
return pow(a, (p - 1) // 2, p)
assert legendre(a, p) == 1, "不是二次剩余"
q = p - 1
s = 0
while q % 2 == 0:
q //= 2
s += 1
if s == 1:
return (pow(a, (p + 1) // 4, p))
for z in range(2, p):
if p-1 == legendre(z,p):
break
c = pow(z, q, p)
r = pow(a, (q + 1) // 2, p)
t = pow(a, q, p)
m = s
t2 = 0
while (t - 1) % p != 0:
t2 = (t * t) % p
for i in range(1, m):
if (t2 - 1) % p == 0:
break
t2 = (t2 * t2) % p
b = pow(c, 1<< (m - i - 1), p)
r = (r * b) % p
c = (b * b) % p
t = (t * c) % p
m = i
return r
m=bytes_to_long(b"flag{Ooooh!you_find_me!!!}")
print(m)
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
n=p*q
c=pow(m,2,p)
print(c)
print(long_to_bytes(gmpy2.iroot(c,2)[0]))
mp=Tonelli(c,p)
mq=Tonelli(c,q)
gcd,yp,yq=gmpy2.gcdext(p,q)
a=(yp*p*mq+yq*q*mp)%n
b=n-a
c=(yp*p*mq-yq*q*mp)%n
d=n-c
for i in (a,b,c,d):
print(long_to_bytes(m))
Tonelli算法针对两种情况的p求二次剩余，ctf wiki 上只给出了p=3 mod 4的情况
得到结果
wiki上没有提到CRT而是直接套用了CRT的公式，搞得一般人看不懂他在做什么东西。。（我反正一开始很疑惑
其实这个题也可以用sagemath和sympy库直接求解：
由于sagemath的环境奇奇怪怪，跑不出mq，于是把mp和mq在python里跑出来再拉到sagemath上。
import gmpy2
from Crypto.Util.number import *
from sympy import nthroot_mod
m=bytes_to_long(b"flag{Ooooh!you_find_me!!!}")
#print(m)
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
n=p*q
#print(n)
c=pow(m,2,p)
#print(c)
#print(long_to_bytes(gmpy2.iroot(c,2)[0]))
mp=nthroot_mod(c,2,p)
mq=nthroot_mod(c,2,q)
mp,mq=44524585842042881800196269370782813912,20185348016726685214067337751536108644
res=CRT_list([mp,mq], [p,q])
print(res)
例题
然后我在ctfshow上发现了一道奇奇怪怪的题目
源码：
from Crypto.Util.number import bytes_to_long from secrets import p,q,r,s,t,flag n = p * q * r * s * t e = 2 m = bytes_to_long(os.urandom(500) + flag) c = pow(m,e,n) print(p,q,r,s,t,sep='n') print(c) ''' 145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263 116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763 157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531 100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679 93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447 9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129 '''
ctfshow上这道题奇怪之处在于n由5个素因数组成，由于rabbin的特殊性，这让解密更加复杂
这里求解用到了sympy库的nthroot_mod函数，同样可以用我在上文给出的Tonelli算法求二次剩余，但二次剩余求解只能求出来正整数解，需要手动加上在素因数域下的负数解
nthroot_mod用于求解
x
n
≡
a
m
o
d
p
x^nequiv a ~mod~p
xn≡a mod p
在找到每一个素因数的解后，遍历所有可能的组合利用CRT求解。
exp:
p=145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263 q=116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763 r=157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531 s=100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679 t=93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447 c=9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129 e = 2 P.=PolynomialRing(Zmod(p),implementation='NTL') f=a^e-c mpx=f.monic().roots() P.=PolynomialRing(Zmod(q),implementation='NTL') g=a^e-c mqx=g.monic().roots() P.=PolynomialRing(Zmod(r),implementation='NTL') h=a^e-c mrx=h.monic().roots() P.=PolynomialRing(Zmod(s),implementation='NTL') i=a^e-c msx=i.monic().roots() P.=PolynomialRing(Zmod(t),implementation='NTL') j=a^e-c mtx=j.monic().roots() print("over") for mpp in mpx: x=mpp[0] for mqq in mqx: y=mqq[0] for mrr in mrx: z=mrr[0] for mss in msx: a=mss[0] for mtt in mtx: b=mtt[0] solution=hex(CRT_list([int(x),int(y),int(z),int(a),int(b)], [p,q,r,s,t]))[2:] if b'ctfshow'.hex() in solution: print(bytes.fromhex(solution))
