跳转至

P19.Franklin-Reiter攻击脚本

P19.sage Franklin-Reiter攻击脚本

网上脚本

https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage 

#sage

# Franklin-Reiter 攻击 RSA。
# 如果两条消息的区别仅在于两条消息之间的已知固定差异
# 并且是在相同的 RSA 模数 N 下进行 RSA 加密的
# 那么就可以恢复它们。

# 输入是模数，已知差异，密文1，密文2。
# Ciphertext 1 对应两个明文中较小的一个。（没有添加固定差异的那个）
def franklinReiter(n,e,r,c1,c2):
    R.<X> = Zmod(n)[]
    f1 = X^e - c1
    f2 = (X + r)^e - c2
    # coefficient 0 = -m, which is what we wanted!
    return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[0])

  # GCD is not implemented for rings over composite modulus in Sage
  # so we do our own implementation. Its the exact same as standard GCD, but with
  # the polynomials monic representation
def compositeModulusGCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

def CoppersmithShortPadAttack(e,n,C1,C2,eps=1/30):
    """
    Coppersmith's Shortpad attack!
    Figured out from: https://en.wikipedia.org/wiki/Coppersmith's_attack#Coppersmith.E2.80.99s_short-pad_attack
    """
    import binascii
    P.<x,y> = PolynomialRing(ZZ)
    ZmodN = Zmod(n)
    g1 = x^e - C1
    g2 = (x+y)^e - C2
    res = g1.resultant(g2)
    P.<y> = PolynomialRing(ZmodN)
    # Convert Multivariate Polynomial Ring to Univariate Polynomial Ring
    rres = 0
    for i in range(len(res.coefficients())):
        rres += res.coefficients()[i]*(y^(res.exponents()[i][1]))

    diff = rres.small_roots(epsilon=eps)
    recoveredM1 = franklinReiter(n,e,diff[0],C1,C2)
    print(recoveredM1)
    print("Message is the following hex, but potentially missing some zeroes in the binary from the right end")
    print(hex(recoveredM1))
    print("Message is one of:")
    for i in range(8):
        msg = hex(Integer(recoveredM1*pow(2,i)))
        if(len(msg)%2 == 1):
            msg = '0' + msg
        if(msg[:2]=='0x'):
            msg = msg[:2]
        print(binascii.unhexlify(msg))

def testCoppersmithShortPadAttack(eps=1/25):
    from Crypto.PublicKey import RSA
    import random
    import math
    import binascii
    M = "flag{This_Msg_Is_2_1337}"
    M = int(binascii.hexlify(M),16)
    e = 3
    nBitSize =  8192
    key = RSA.generate(nBitSize)
    #Give a bit of room, otherwhise the epsilon has to be tiny, and small roots will take forever
    m = int(math.floor(nBitSize/(e*e))) - 400
    assert (m < nBitSize - len(bin(M)[2:]))
    r1 = random.randint(1,pow(2,m))
    r2 = random.randint(r1,pow(2,m))
    M1 = pow(2,m)*M + r1
    M2 = pow(2,m)*M + r2
    C1 = Integer(pow(M1,e,key.n))
    C2 = Integer(pow(M2,e,key.n))
    CoppersmithShortPadAttack(e,key.n,C1,C2,eps)

def testFranklinReiter():
    p = random_prime(2^512)
    q = random_prime(2^512)
    n = p * q # 1024-bit modulus
    e = 11

    m = randint(0, n) # some message we want to recover
    r = randint(0, n) # random padding

    c1 = pow(m + 0, e, n)
    c2 = pow(m + r, e, n)
    print(m)
    recoveredM = franklinReiter(n,e,r,c1,c2)
    print(recoveredM)
    assert recoveredM==m
    print("They are equal!")
    return True

题目1

from Crypto.Util.number import *
from random import choice
import string
from flag import flag

def getIv(length,chars=string.ascii_lowercase):
    return ''.join([choice(chars) for i in range(length)])

p = getPrime(1024)
q = getPrime(1024)
iv = getIv(128)

key1 = bytes_to_long(flag+iv)
key2 = bytes_to_long(iv)

e = 3
print 'n:' + str(p*q)
c1 = pow(key1,e,p*q)
c2 = pow(key2,e,p*q)

print 'c1:' + str(c1)
print 'c2:' + str(c2)

x = key1/key2
y = key1-x*key2
key1=x*key2+y


print 'x:' + str(x)
print 'y:' + str(y)

# output:
n=18099247369280154886617000375109767499806054172740063389012130770186820932961360864498732850525922466534945118800932145228805671351976586517097622365680011651402327925464073182713293531130034756251505774357417055627671229271867926990490595666312835905910514734764729504786992310448996071206128488211439271233843142630939565246707372296583601804184804171689260854956262942235631405717696974169377626396323676395636456740120025184398476594314662368359312356066266921270189494622506635066969735080655725839847984616974215284857408784397344862523720171616739915198953492024993048307867785945156942213152962536432345964739
c1=12278575945470897872640453814770538959516698979717179227690510266529921428552864312660132740788416401327102285180588038083079258311881620201133998229854752124927460819177711379328404288010908880844043596472423294384267295041524633599162192148584399505960857935034928148929492625945646997837039619205559476017169925713468855198646629226970777687397537720214045661626920833445827989359857671018875074072055022703115700566419215341376615131689314020746375076743801434662693872661942545103307966098491064656551141436523806773529181866000500420523710554658948977262516303583655752676734847641890080943847492535926834052488
c2=17408296326028739312453312633484317596943826388625453121732287745283275892186527757287755028016444735036842917880385034442965065523813174163945799579491327454221196284056233455567244848717704030947162883942273297422509937269431814260733969129102074843485655311252111459010777945499431139524012532947251982056639653098247711079544046418704543343537501388589717979520036378098389654456014224822916973106504500942515154126504282811270117380780048894037581126326329800132358724785374395728605324605424194037625702457971360093340866984155213328508506733775129948622882145937096019437059787874064306250117133787681357927186
x=94819009910611490937147710332193973830402125343380796
y=27036298270176650012154148050982037588069778308019261952420224460786523779956477136773576099293451667012578253132502506974471829679519804802324747292357969625762476160905899712303273534268489228000459887114964986912314483751635173113737622875478746013228230937327043213246022641974495178269021953810671692021

解密脚本

因为key2 小于 key1 需要替换下c2 和 c1 的位置 

def franklinReiter(n,e,c1,c2,x1,y1):
    R.<X> = Zmod(n)[]
    f1 = X^e - c2
    f2 = (X*x1+ y1)^e - c1
    # coefficient 0 = -m, which is what we wanted!
    return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[0])

  # GCD is not implemented for rings over composite modulus in Sage
  # so we do our own implementation. Its the exact same as standard GCD, but with
  # the polynomials monic representation
def compositeModulusGCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

n=18099247369280154886617000375109767499806054172740063389012130770186820932961360864498732850525922466534945118800932145228805671351976586517097622365680011651402327925464073182713293531130034756251505774357417055627671229271867926990490595666312835905910514734764729504786992310448996071206128488211439271233843142630939565246707372296583601804184804171689260854956262942235631405717696974169377626396323676395636456740120025184398476594314662368359312356066266921270189494622506635066969735080655725839847984616974215284857408784397344862523720171616739915198953492024993048307867785945156942213152962536432345964739
c1=12278575945470897872640453814770538959516698979717179227690510266529921428552864312660132740788416401327102285180588038083079258311881620201133998229854752124927460819177711379328404288010908880844043596472423294384267295041524633599162192148584399505960857935034928148929492625945646997837039619205559476017169925713468855198646629226970777687397537720214045661626920833445827989359857671018875074072055022703115700566419215341376615131689314020746375076743801434662693872661942545103307966098491064656551141436523806773529181866000500420523710554658948977262516303583655752676734847641890080943847492535926834052488
c2=17408296326028739312453312633484317596943826388625453121732287745283275892186527757287755028016444735036842917880385034442965065523813174163945799579491327454221196284056233455567244848717704030947162883942273297422509937269431814260733969129102074843485655311252111459010777945499431139524012532947251982056639653098247711079544046418704543343537501388589717979520036378098389654456014224822916973106504500942515154126504282811270117380780048894037581126326329800132358724785374395728605324605424194037625702457971360093340866984155213328508506733775129948622882145937096019437059787874064306250117133787681357927186
x=94819009910611490937147710332193973830402125343380796
y=27036298270176650012154148050982037588069778308019261952420224460786523779956477136773576099293451667012578253132502506974471829679519804802324747292357969625762476160905899712303273534268489228000459887114964986912314483751635173113737622875478746013228230937327043213246022641974495178269021953810671692021
e=3
key2=franklinReiter(n,e,c1,c2,x1,y1)
print(key2)
print(key2*x1+y1)
#6888963054258642613740325434330669608753226058634053294961493623175402123423076765486521793459129361281449088315708197565085083193444886554420466104040516489271824213587620932188993548052848705998448234910002066319419375438874205309976091920990411697914875778848108746628535295745926285102414338027810783987711072435382043887546827768330700843751035424140257393
#flag{98dd715f2e03fe16}

题目2

from secret import flag
from Crypto.Util.number import *

m1 = bytes_to_long(flag)
N = getPrime(512)*getPrime(512)
e = 17

c1 = pow(m1, e, N)

a = getRandomNBitInteger(512)
b = getRandomNBitInteger(512)
m2 = a*m1 + b
c2 = pow(m2, e, N)

print(N, a, b, c1, c2, sep="\n")

n=51296885372346449295388453471330409021784141081351581975478435681552082076338697136130122011636685327781785488670769096434920591920054441921039812310126089859349902066456998315283909435249794317277620588552441456327265553018986591779396701680997794937951231970194353001576159809798153970829987274504038146741
a=13256631249970000274738888132534852767685499642889351632072622194777502848070957827974250425805779856662241409663031192870528911932663995606616763982320967

b=12614470377409090738391280373352373943201882741276992121990944593827605866548572392808272414120477304486154096358852845785437999246453926812759725932442170



c1=18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310283844080111189381106274103089079702496168766831316853664552253142
c2=14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464950939837343822566667533463393026895985173157447434429906021792720

解题脚本

def franklinReiter(n,e,c1,c2,a,b):
    R.<X> = Zmod(n)[]
    f1 = X^e - c1
    f2 = (X*a+ b)^e - c2
    # coefficient 0 = -m, which is what we wanted!
    return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[0])

  # GCD is not implemented for rings over composite modulus in Sage
  # so we do our own implementation. Its the exact same as standard GCD, but with
  # the polynomials monic representation
def compositeModulusGCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

n=51296885372346449295388453471330409021784141081351581975478435681552082076338697136130122011636685327781785488670769096434920591920054441921039812310126089859349902066456998315283909435249794317277620588552441456327265553018986591779396701680997794937951231970194353001576159809798153970829987274504038146741
a=13256631249970000274738888132534852767685499642889351632072622194777502848070957827974250425805779856662241409663031192870528911932663995606616763982320967
b=12614470377409090738391280373352373943201882741276992121990944593827605866548572392808272414120477304486154096358852845785437999246453926812759725932442170
c1=18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310283844080111189381106274103089079702496168766831316853664552253142
c2=14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464950939837343822566667533463393026895985173157447434429906021792720
e=17

m=franklinReiter(n,e,c1,c2,a,b)
print(m)
print(hex(m))
#0x666c61677b61353933353931612d333734392d636335322d306332372d6538393766616332633936377d