RSA相关算法

gmpy2相关函数

import gmpy2
gmpy2.mpz(n)#初始化一个大整数
gmpy2.mpfr(x)# 初始化一个高精度浮点数x
d = gmpy2.invert(e,n) # 求逆元，de = 1 mod n
C = gmpy2.powmod(M,e,n)# 幂取模，结果是 C = (M^e) mod n
gmpy2.is_prime(n) #素性检测
gmpy2.gcd(a,b) #欧几里得算法，最大公约数
gmpy2.gcdext(a,b) #扩展欧几里得算法
gmpy2.iroot(x,n) #x开n次根 返回的第一个值表示开方后结果 第二个值表示是否能开尽

各方信息

通信者A(解密方):掌握全部数据 p、q、公钥(n，e)、密文c

通信者B(加密方): 公钥(e，n)、密文c、明文m

攻击者C:公钥(e，n）、密文c

通信者A通过p、q计算得到d然后根据私钥（e，n）解出明文m

解密者角度

1.已知p、q、e求d

import libnum
p = 473398607161
q = 4511491
e = 17
d = libnum.modular.invmod(e, (p-1)*(q-1))
print(d)

##通过primefac也可以实现求d 不过prime只支持python2环境
import primefac
d=prime.modinv(e,(p-1)*(q-1))%((p-1)*(q-1))

##通过gmpy2也可以实现求d
import gmpy2
#其中gmpy2.mpz()函数起初始化大整数的作用
p=gmpy2.mpz($p) 
q=gmpy2.mpz($q)
e=gmpy2.mpz($e)
d=gmpy2.invert(e,(p-1)*(q-1))
print(d)

攻击者角度

攻击者与解密者的信息差距往往就是p、q，其目标往往是获取密文m

模数分解

1 对于n比较小(256bit)的情况，可以通过yafu直接模数分解n，通过p、q、e求得d，而后

from Crypto.Util.number import long_to bytes
m=pow(c,d,n)
print(long_to_bytes(m))
#long_to_bytes实现将m转化为字符串

2 yafu的分解同时集成了费马分解和Pollard_rho分解，所以有的时候即使n的长度是1024bit，也会由于其中一个素因子太小或两个因子相差不大成功分解。

3 公约数模数分解

进行两次通信会产生两个n，如果通信者A在两次通信中生成的大素数有一个是相同的，那攻击者C就可以对两次的n进行公约数计算从而得到n

p=gmpy2.gcd(n1,n2)
q1=n1/p
q2=n2/p

小指数明文爆破

加密方B得到A的公钥(n，e)，如果e比较小，则会$m^e<n$,则$c=m^e$ 此时直接对c开e次方就得到m，但有时候并不是这么极端但可能$m^e$也没有超过n太多，于是可以爆破出m

from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, isPrime
n = 47966708183289639962501363163761864399454241691014467172805658518368423135168025285144721028476297179341434450931955275325060173656301959484440112740411109153032840150659
e = 3
c = 10968126341413081941567552025256642365567988931403833266852196599058668508079150528128483441934584299102782386592369069626088211004467782012298322278772376088171342152839
import gmpy2
i = 0
while 1:
  if (gmpy2.iroot(c + i * n, 3)[1] == 1):#第二个参数[1]判断能否开尽
    print(long_to_bytes(gmpy2.iroot(c + i * n, 3)[0]))#第一个参数[0]表示开方后得到的数
    break
  i = i + 1

选择密文攻击

攻击方可以对任意密文解密，除了C。那可以先求出C在N上的逆元$C^{-1}$,然后求$C^{-1}$的明文$M^{'}$,$M^{'}$即为明文M的逆元。

LLL-attack

e太小，m部分泄露或者p泄露三分之二的情况下使用。用于LLLattack的sage代码。

Wiener Attack & Boneh Durfee Attack

一般e很大，远超65537，就基本可以确定是Wiener Attack。可以采用维纳攻击脚本。

共模攻击

A在两次通信中采用相同的n，B对相同的m进行加密。采用以下脚本解密

from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime,isPrime
import gmpy2
def same_n_attack(n,e1,e2,c1,c2):
    
    def egcd(a, b):
        x, lastX = 0, 1
        y, lastY = 1, 0
        while (b != 0):
            q = a // b   #整除
            a, b = b, a % b
            x, lastX = lastX - q * x, x
            y, lastY = lastY - q * y, y
        return (lastX, lastY)

    s = egcd(e1, e2)
    s1 = s[0]
    s2 = s[1]
    if s1<0:
        s1 = - s1
        c1 = gmpy2.invert(c1, n)
        if c1<0:
            c1+=n
    elif s2<0:
        s2 = - s2
        c2 = gmpy2.invert(c2, n)
        if c2<0:
            c2+=n
    m=(pow(c1,s1,n)*pow(c2,s2,n)) % n
    return m
n1=21660190931013270559487983141966347279666044468572000325628282578595119101840917794617733535995976710097702806131277006786522442555607842485975616689297559583352413160087163656851019769465637856967511819803473940154712516380580146620018921406354668604523723340895843009899397618067679200188650754096242296166060735958270930743173912010852467114047301529983496669250671342730804149428700280401481421735184899965468191802844285699985370238528163505674350380528600143880619512293622576854525700785474101747293316814980311297382429844950643977825771268757304088259531258222093667847468898823367251824316888563269155865061
e1=65537
c1=11623242520063564721509699039034210329314238234068836130756457335142671659158578379060500554276831657322012285562047706736377103534543565179660863796496071187533860896148153856845638989384429658963134915230898572173720454271369543435708994457280819363318783413033774014447450648051500214508699056865320506104733203716242071136228269326451412159760818676814129428252523248822316633339393821052614033884661649376604245744651142959498917235138077366818109892738298251161767344501687113868331134288984466294415889635863660753717476594011236542159800099371872396181448655448842148998667568104710807411358117939831241620315
n2=21660190931013270559487983141966347279666044468572000325628282578595119101840917794617733535995976710097702806131277006786522442555607842485975616689297559583352413160087163656851019769465637856967511819803473940154712516380580146620018921406354668604523723340895843009899397618067679200188650754096242296166060735958270930743173912010852467114047301529983496669250671342730804149428700280401481421735184899965468191802844285699985370238528163505674350380528600143880619512293622576854525700785474101747293316814980311297382429844950643977825771268757304088259531258222093667847468898823367251824316888563269155865061
e2=70001
c2=8180690717251057689732022736872836938270075717486355807317876695012318283159440935866297644561407238807004565510263413544530421072353735781284166685919420305808123063907272925594909852212249704923889776430284878600408776341129645414000647100303326242514023325498519509077311907161849407990649396330146146728447312754091670139159346316264091798623764434932753276554781692238428057951593104821823029665203821775755835076337570281155689527215367647821372680421305939449511621244288104229290161484649056505784641486376741409443450331991557221540050574024894427139331416236263783977068315294198184169154352536388685040531
print (long_to_bytes(same_n_attack(n1,e1,e2,c1,c2)))

广播攻击

加密的过程中e较小，且这几次加密过程中，加密信息相同，即

$$ c_1\equiv m^e\mod n_1\\c_2\equiv m^e\mod n_2\\c_3\equiv m^e\mod n_3 $$

那么通过中国剩余定理)，计算$c_x\equiv m^3\mod n_1n_2n_3$,然后对$c_x$开e次方根得到m

from gmpy2 import iroot
from gmpy2 import invert
n1 = 24451423288348328116705189839080049401203825573696682939697089229515670854259668024738917571672083091736391032222439276176190670330149788177234868093407333559601300076140811141390059132774991537248278852195374559377914946861163565102316087142050792987559132773464700849304645152015574005517342653095585568809642839372678062663523564820583166717521739237792276166111668361172039147292768193129632684171172002382830408379067354719706121993642173739213280355600134781117773160460528207346288478815871296055864733062408148349209845936379646848651625713969508821074528754713838207135211670970387019665490891554278609420811
e1 = 3
c1 = 15739875616514630953136118518167425336566344729401649295136386816279793948062937416837879973892217898183001604612634670589995445217883630705454669275572015747596408894160611264926362963690714019483949272102316017165459832305673786710006588680357259384309205799575411881386856841704490851908762197421112221154073096284400634344102924080733996136266689995846872435464641531701655540246069568899209408835603371228683787516867834686720338208876553150308049787749151860312456421834317148300953317025532490631516416557696361667176077040251336722246089493549323185006889559952252279223464226121335279699764156011687694705461

n2 = 26371477190418742303888775088555323015207366776923126851773114394065723645672368088814181502360410900641156468215436455676418853504498893778165004679238083105115284038962860549618453609620564211541961829192628570279313244745190283361932206525212450405965917102560591225166296026203946023621569117063731896380036557814205848678875929376998512733964346619930409595564029979283595842765495546420008144195139735377286287069524605209733051251754274764107934939709473307270046001810101986138988618191726147463699979330655595693169524011001045064479429960522005088680268206848597198271413010280267566035795254656463702698823
e2 = 3
c2 = 24491112204092744341358638089215970530809389175921723500286573918429636398447936137595118862398236862698779775682952162653546124550629784165964386769387726103595283121496975198529062258433280603856760220088192538482626338903512801906921311030654216689591936509151350395249697750541120735732723071144598196884071338084546259983640953398715738096470608250955118848652845310318107343620885777444921011193265422744126912733993340865179850073221405567439254502574578925781409459433294016640150862732200176452820665011738329510188452740687455054869063245100602567671645540401390791588456748406543904714454899841545079587056

n3 = 27487047904330959883767333331462030929928491213958156653308086307319240141800614908094361257431882391215313284438555713825838241511527538964789800420812050047003596770148880871768715848882256199410164419506052779212555843479717842656396150794330441002831153507102960164073640832600708150242550799365929109808430251649175060381698677302608174255794872628187783088414186634174367531662043643358473337581486905937469115169466276315070659112396585619309358563546478189304744220858913259592690589213905377550443295883410708775472142360727764158039142452443204569417848208594378792577246174638639911159712430937128321437067
e3 = 3
c3 = 1657721854648476317520442150896650605711954769246991233391881094037826060908691858031485703087740392488258133124921363936766424042899719887649974751632127107022899794941279627494196541358161346953558285922698679387524282160943205189313406083166270966025941354796192171615197811422473937679394910921908268579426452496116103480709293429547721026538860977229195889575005308631157579567095561669277297494272383133948347665024419752146336618756926080138955963546588675787675378048078021878779569010236088293191739741596470893703755598233769968042607918446569365734945861279726941898996019192367675358423090129022372729450
m1, m2, m3 = invert(n2 * n3, n1), invert(n1 * n3, n2), invert(n1 * n2, n3)
x = (c1 * (m1 % n1) * n2 * n3 + c2 * (m2 % n2) * n1 * n3 + c3 * (m3 % n3) * n2 * n1) % (n1 * n2 * n3)
# print(x)
m, n = iroot(x, e1)
print(m)