rsa中的共模攻击

介绍

共模攻击是指在不分解d的情况下依旧可以求出m的一种算法，常见给出了c1,c2：

c1 = pow(m , e1 , N)
c2 = pow(m , e2 , N)

要求gcd(e1 , e2)=1,即e1,e2互质,那么则有:

e1*s1 + e2*s2 = 1
// s1,s2一正一负

可以有:m = ( c1^s1 * c2^s2) % N，下面给出证明：

注意：此处并不是说c的s次方，而是c关于N的s次逆元是多少。

(c1^s1 * c2^s2) % N = ( ((m^e1)%N) ^ s1 * (((m^e2)%N) ^ s2)
    				// 将%N 去除，具体可以看开头文章
                    = ( m ^ (e1*s1 + e2*s2))%N
                    = m     

注意

假定s2为负数，并不是对c2开根号，而是求c2的逆元，交给pow函数即可

例题

from Crypto.Util.number import getPrime, inverse, long_to_bytes, bytes_to_long
from sympy import gcd

key_size = 1024
p = getPrime(key_size // 2)
q = getPrime(key_size // 2)
N = p * q
phi = (p - 1) * (q - 1)
e1 = 3
e2 = 7
message = b"NSSCTF{...............................................}"
m = bytes_to_long(message)

assert gcd(m, N) == 1

c1 = pow(m, e1, N)
c2 = pow(m, e2, N)

print(f"N = {N}")
print(f"e1 = {e1}")
print(f"c1 = {c1}")
print(f"e2 = {e2}")
print(f"c2 = {c2}")

#N =  80722936701364382749961243326484006977187702986017980842794443374132452156776306032868217795522046975068822236770836452911408536092460646410756678157902792329645719935468879960944028782788489463895870961967670931567205550383999951787250211085264314795753745003815839218062934564501884684565508432346164094171
#e1 = 3
#c1 = 77027474990431732719325428265107176934045610651944725251406683442684093440239073195437770144166442593914418380343458827052860752131667771506129334676070396374008929588455988149871039697387983766750148969695215583137356681988572655848921827794639096404716760310059622671470680330144220097050812716421370445797
#e2 = 7
#c2 = 13491956530007991248882899018888359080930858500993821006822695375714947537976202424265808646466853291165511243721829370428583392329886743499827454177786585477285598196204906977043127274613692623229137936467994670727274820568522666762615055848367486507714640497446688083840123758417442971555904294548595887600

题解

e1 和 e2 明显互质，可以用共模攻击，先求出s1和s2，随便选取一个即可，然后直接求出m即可：

from Crypto.Util.number import inverse, long_to_bytes
from sympy import *

# 输入的 RSA 参数
N = 80722936701364382749961243326484006977187702986017980842794443374132452156776306032868217795522046975068822236770836452911408536092460646410756678157902792329645719935468879960944028782788489463895870961967670931567205550383999951787250211085264314795753745003815839218062934564501884684565508432346164094171
e1 = 3
c1 = 77027474990431732719325428265107176934045610651944725251406683442684093440239073195437770144166442593914418380343458827052860752131667771506129334676070396374008929588455988149871039697387983766750148969695215583137356681988572655848921827794639096404716760310059622671470680330144220097050812716421370445797
e2 = 7
c2 = 13491956530007991248882899018888359080930858500993821006822695375714947537976202424265808646466853291165511243721829370428583392329886743499827454177786585477285598196204906977043127274613692623229137936467994670727274820568522666762615055848367486507714640497446688083840123758417442971555904294548595887600

for i in range(99):
    for j in range(99):
        if e1 * i - e2 * j == 1:
            print(i , j, e1 * i + e2 * j )
s1 = 5
s2 = -2
m = (pow(c1, s1, N) * pow(c2, s2, N)) % N
print(long_to_bytes(m))

特例-gcd(e1,e2) != 1

上述说了，共模攻击是要求e1和e2互质，即(e1,e2)=1，才有e1*s1+e2*s2=1,才可以继续进行后续的操作
但是若(e1,e2)!=1，而有(e1,e2)=e呢？此时是有e1*s1+e2*s2=e的，按照上述的推理，我们得到的应该是

(c1^s1 * c2^s2) % N = (m ^ e)%N

分两种情况：

1: m^e < N: 那么此时直接开e次根即可

2: m^e > N:此时直接开根答案并不对

M = (c1^s1 * c2^s2) % N = (m ^ e)%N
-> m^e = k*n + M (k=1,2,.....)

例题

e1*e2= 59653
n= 16282992590526808657350657123769110323293742472515808696156540766049532922340638986423163288656942484229334024198335416611687418341772216996129634991032127943095069143600315325916614910606100091970611448259491799589221889445348698100959509165262891180065554743420149168801638644589921791426690475846945077068114953844817073866258377206796158690941199907230130273657375727245023893672164113928189304228859412794067127721813637080447782673535996272223836127807775157150041664783263093604946744032762535394974814371771505843653571711445892969781888188805943142126747365056482511805191315474848971218180999336497135314654469910566730389765499603897685968204361422568601724914800686608628299192714352963744010136960423806304763245890692476493455775025753944860040020178234660999290356849442926396627701588938894161779071628447041006556793933320976506046066961014953196791133933438500843139378274786265308568167479880984705152809744111382599071097574636570516674122980589207824718402382459624138317432883921371298272851693734695823787102433937406420318428888224246291987404818042038201886113203158444083427668636941
c1= 15508846802476602732219982269293312372397631462289816533805702700260237855119470146237752798828431803179124957728439730580289236458563016332461725094295883030444173189424666004498359269921250956676320570006883951982237098373954348825003467019876101438948387668628518937831820206221522881150831840296199498447304138839838135264071071817072965792514115711621435317078108239744829134467948386247696344881838815422262901903767893118533887779588425725845820071451782420200868341564360095012698956683395031351656817392008005928265838760875070634021907630535014959579709368637536268853337028760833769278841040734409299575870823873616769863828516877971432999417800417684146077045836940988096634144368727546539602310924702126212020003620219218637652874119299016382481718659448722433296761241365473608283436835986184098161365747699791248301452334044327014782249692551362625130537300221641910570569803981153117200694806974917501061411963827755822672178568783269357196133308719688843211664095412087717861154226475203597889635926903753481174280305996204091501578865951177135086807765873529089048911740160698421289371229606
c2= 7038544062804420883340530319534054090343999593726615071597649914714397773106261660516938820194721330117082799104642674913839235601210294807255855747823709326405317366422536981850436536877639492293904186333547681934006229055311359852552059601531864585759120757265084674695094298158389804437120173997679271166467086009884419942249925895393890707373985126949313101489352481737754459985522998334847972008827503987883850638250024631354158979424169551575287515128697843093987592614974905262077415255065744686115142126350167970451060399517705823298929164793769442986603707135790651560436497661713972277808036463771768932747376668116480068277125579165831615220097562066809632099809702980365194257899499384219864311379004681733844738981954144617140038448109869114888325128710654235506628539192955240723379334422880368605005772426413018696218105733457019400100498450734710865067764542737004071080719589912326985050985424145053072697267879019954400205613591419766583673115931337146967400159040252514654983240188915104134405655336152730443436887872604467679522955837013574944135975481174502094839012368918547420588186051

EXP

直接上题解

from Crypto.Util.number import inverse, long_to_bytes
import libnum
import gmpy2

# 数据均在上面，为了方便看，就不填入了
n = ...
c1 = ...
c2 = ...
# e1 * e2 = 59653
e1e2 = 59653

def rsa_gong_N_def(e1, e2, c1, c2, n):
    s = gmpy2.gcdext(e1, e2)
    s1, s2 = s[1], s[2]

    if s1 < 0:
        s1, c1 = -s1, gmpy2.invert(c1, n)
    elif s2 < 0:
        s2, c2 = -s2, gmpy2.invert(c2, n)

    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
    return m

def de(c, e, n):
    for k in range(1000):
        mk = c + n * k
        flag, true1 = gmpy2.iroot(mk, e)
        if true1:
            return flag
    return None

for e1 in range(2, e1e2):
    if e1e2 % e1 == 0:
        e2 = e1e2 // e1
        c = rsa_gong_N_def(e1, e2, c1, c2, n)
        e = gmpy2.gcd(e1, e2)
        m1 = de(c, e, n)
        if m1 and b'flag' in long_to_bytes(int(m1)):
            print(long_to_bytes(int(m1)))

下面对exp解释：

先找到合适的e1,e2,以及对应的M

gmpy2.gcdext(e1,e2):

返回一个包含三个值的元组

s[0]->gcd(e1,e2)，s[1]->s1, s[2] -> s2 (e1s1 + e2s2 ==gcd(e1,e2))

gmpy2.invert(c, n)

计算c关于模m的逆元

2.c(M)带入爆破，此时满足 mk = c + n * k

gmpy2.iroot

用于计算整数 x 的 k 次根。它返回一个元组 (root, is_exact)，其中：

root：x 的 k 次根的整数部分。

is_exact：一个布尔值，指示 root 是否是 x 的确切 k 次根

3.判断爆破出来的是否包含flag即可