Franklin-Reiter related message attack

Article directory

  • Knowledge import:
  • Question one
      • Title description:
      • Topic analysis:
  • Question two
      • Title description:
      • Topic analysis:
  • Question three
      • Title description:
      • Topic analysis:
  • Harvest and experience:

Knowledge introduction:

  • Summarize:
    Franklin-Reiter related-message attack (Franklin-Reiter related-message attack): If there is a known fixed difference between two messages, and RSA encryption under the same modulus n, it is possible to recover both information
  • To put it simply, the two plaintexts m and m + a are encrypted under the same e and n, then m can be cracked
If there are only known fixed differences between the two messages

and encrypted under the same RSA modulo N

then it is possible to restore them simultaneously

m1 = bytes_to_long(flag)

m2 = a * m1 + b

c1 = pow(m1,e,n)

c2 = pow(a * m1 + b,e,n)

Where c1, c2, e, n are all known, then m1, m2 can be cracked

Question 1

Description of topic:

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="\\
")

# 512968853723464492953884534713304090217841410813515819754784356815520820763386971361301220116366853277817854886707690964 349205919200544419210398123101260898593499020664569983152839094352497943172776205885524414563272655530189865917793967016809 97794937951231970194353001576159809798153970829987274504038146741
# 132566312499700002747388881325348527676854996428893516320726221947775028480709578279742504258057798566622414096630311928 70528911932663995606616763982320967
# 126144703774090907383912803733523739432018827412769921219909445938276058665485723928082724141204773044861540963588528457 85437999246453926812759725932442170
# 186176980951225973557521785848607642217361561398444014009429590005601808685950585722643302574906450797923217789264623004 106539707226193320986015153995262458087185181535188244041673743610984243252968725873627928398315785894074417390405783393102 83844080111189381106274103089079702496168766831316853664552253142
# 140913615284140939006884402421523271151092565071337287997582899184629707241093434104645372036897274095907964721772958357 105717005018954843009796225062989619990016410591794496556294810724022349658316979159390347698044374525289215991258234124649 50939837343822566667533463393026895985173157447434429906021792720

Topic Analysis:

Typical Franklin-Reiter related message attack, directly upload the problem-solving code:

n=512968853723464492953884534713304090217841410813515819754784356815520820763386971361301220116366853277817854886707690 964349205919200544419210398123101260898593499020664569983152839094352497943172776205885524414563272655530189865917793967016 80997794937951231970194353001576159809798153970829987274504038146741
a=132566312499700002747388881325348527676854996428893516320726221947775028480709578279742504258057798566622414096630311928 70528911932663995606616763982320967
b=126144703774090907383912803733523739432018827412769921219909445938276058665485723928082724141204773044861540963588528457 85437999246453926812759725932442170
c1=18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300 410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310 283844080111189381106274103089079702496168766831316853664552253142
c2=14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835 710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464 950939837343822566667533463393026895985173157447434429906021792720
e=17

import libnum
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]) # coefficient

  # 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)

m=franklinReiter(n,e,c1,c2,a,b)
print(libnum.n2s(int(m)))
# flag{a593591a-3749-cc52-0c27-e897fac2c967}

or (essentially the same, a bit more concise):

import libnum
n=512968853723464492953884534713304090217841410813515819754784356815520820763386971361301220116366853277817854886707690964 349205919200544419210398123101260898593499020664569983152839094352497943172776205885524414563272655530189865917793967016809 97794937951231970194353001576159809798153970829987274504038146741
a=132566312499700002747388881325348527676854996428893516320726221947775028480709578279742504258057798566622414096630311928 70528911932663995606616763982320967
b=126144703774090907383912803733523739432018827412769921219909445938276058665485723928082724141204773044861540963588528457 85437999246453926812759725932442170
c1=18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300 410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310 283844080111189381106274103089079702496168766831316853664552253142
c2=14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835 710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464 950939837343822566667533463393026895985173157447434429906021792720
e=17
import binascii
def franklinReiter(n,e,c1,c2,a,b):
    PR.<x> = PolynomialRing(Zmod(n))
    g1 = (x)^e - c1
    g2 = (a*x + b)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic() #
    return -gcd(g1, g2)[0]

m=franklinReiter(n,e,c1,c2,a,b)
print(libnum.n2s(int(m)))
# flag{a593591a-3749-cc52-0c27-e897fac2c967}
  • in:
def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic() #
    return -gcd(g1, g2)[0]
  1. Find the greatest common divisor of polynomials using the method of rolling and dividing
  2. In algebra, the leading coefficient of a polynomial is often called the leading coefficient of the polynomial, and changing the polynomial to a form with the leading coefficient of 1 is called reducing the polynomial to monic form
  3. Call the function g1.monic() to convert g1 to a monic polynomial and return the polynomial.
  4. Using g.monic()[0] will return the constant term of the polynomial obtained by dividing g(x) by the bootstrap coefficient
    For example: g.monic() = x + 32412345
    Then: g.monic()[0] = 32412345

Question 2

Description of topic:

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
from functools import reduce
from secret import flag, x, y

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(n)

assert(reduce(lambda x,y:x & amp;y,[(i-5)*i + 6==0 for i in x]))
assert(reduce(lambda x,y:x &y,[(j-15)*j + 44==0 for j in y]))

print(pow(reduce(lambda x,y:x*m + y,x),17,n))
print(pow(reduce(lambda x,y:x*m + y,y),17,n))

# n = 2377259998313521548156317826688436229187657175999128857705747273337490383659133041057495847209039688689530494417620871 148178078128689133406279455528895941039092647447385928984265480953843537743108842235207622506749492465759829895540777148414 615599888307343926642719021282760011936564306527681404427279057345093859683033643037198756190513257973061934119619942089703 498868501277789500255474608038431929812315467144784479908825854191102804171789743481692142415568767786701953539943482546816 022724244137550366491526522369613902540776814646438353755626587501308570242282920081461239511696153843288611691706311974906 8212699
# c1 = 109001515046544097670596992029291002251558922694732718592075137207559036910313625394782429201440735995157469388279378 638351692703837210945426390116652355930659329980915746365259730994260404526268934614490843836634535493546087697277773290360 597463865238439123822895971826153397864371861698113423560858368385209780475611276617771890458886487739491472204114273060983 386164226929141106560048637677193124109061243660005079529603311168781971290104123616366794492818084072145247417327302797777 292515157593204425916636419843630616188652676060073555762300099224218075275982134551129813545909096033175258540703583906220 96569841
# c2 = 172986792207173263746749406121430583307154656933184676928390336423211294334712545474970877469713175673010861247792890 159345826153771655606884474527620431630823949446040620144904467632470082172516114433381030741438099364376945437613699450952 02092750900940979469994907399829695696313513303922266742415376818434932356400626842450088226432584975891966684267889169693 784179602007057794618082922964502985580019096036025026042289731010480820956422900471962359594382786316616583123983131715905 157764537114323530115798093510765321294447352064085913453722963723783965398313850368143493284592664323936129191180941155430 53115450

Topic Analysis:

  • First look at the following string
assert(reduce(lambda x,y:x & amp;y,[(i-5)*i + 6==0 for i in x]))

 1. [(i-5)*i + 6==0 for i in x] Use list comprehension to judge whether the equality is true,
    If it is established, return True, otherwise False, so the final result in the list is [True, True]
 2. Why is it True, because the assert assertion function is used,
    If it is true, it will execute normally, if it is false, it will report an error and the process will be interrupted
    The given question will continue to run normally, so the result should be True,
 3. It can be deduced from this that x = [2,3] (obtained by solving the equation), and it is obvious that y = [4,11] in the next string
 4. The reduce function applies a lambda expression to perform an XOR operation on each element in the list ([True,True]) in turn

 5. PS: 'x' in "lambda x,y:x &y"
        and
        'x' in "[(i-5)*i + 6==0 for i in x]"
        Not the same! ! ! (If it is clear here, then this sentence is really clear!)
  • So launch (I believe everyone will solve the equation)

x = [2,3]
y = [4,11]

  • Next look at the last string:
reduce(lambda x,y:x*m + y,x)

I won’t talk too much about the theory here, let me just give an example.

x = [1,2,3,4]
reduce(lambda x,y:x + y,x), use reduce to accumulate x
x = 1, y = 2, ==>
x + y = 3 ①
x = ①, y = 3, ==>
x + y = 6 ②
x = ②, y = 4, ==>
x + y = 10 ③
That is 1 + 2 + 3 + 4

The final result is 10
Let’s take a more difficult example

x = [1,2,3,4]
reduce(lambda x,y:x*m + y,x), use reduce to accumulate x
x = 1, y = 2, ==>
x*m + y = 1*m + 2 ①
x = ①, y = 3, ==>
x*m + y = (1*m + 2)*m + 3 ②
x = ②, y = 4, ==>
x*m + y = ((1*m + 2)*m + 3)*m + 4 ③

The final result is formula ③

  • From this it can be seen that the topic
reduce(lambda x,y:x*m + y,x) = 2*m + 3
reduce(lambda x,y:x*m + y,y) = 4*m + 11
  • and end up with:
c1 = pow(2*m + 3,17,n)
c2 = pow(4*m + 11,17,n)
  • Another typical Franklin-Reiter related message attack, directly solve the problem with the code
import libnum
n = 23772599983135215481563178266884362291876571759991288577057472733374903836591330410574958472090396886895304944176208711 481780781286891334062794555288959410390926474473859289842654809538435377431088422352076225067494924657598298955407771484146 155998883073439266427190212827600119365643065276814044272790573450938596830336430371987561905132579730619341196199420897034 988685012777895002554746080384319298123154671447844799088258541911028041717897434816921424155687677867019535399434825468160 227242441375503664915265223696139025407768146464383537556265875013085702422829200814612395116961538432886116917063119749068 212699
c1 = 1090015150465440976705969920292910022515589226947327185920751372075590369103136253947824292014407359951574693882793786 383516927038372109454263901166523559306593299809157463652597309942604045262689346144908438366345354935460876972777732903605 974638652384391238228959718261533978643718616981134235608583683852097804756112766177718904588864877394914722041142730609833 861642269291411065600486376771931241090612436600050795296033111687819712901041236163667944928180840721452474173273027977772 925151575932044259166364198436306161886526760600735557623000992242180752759821345511298135459090960331752585407035839062209 6569841
c2 = 1729867922071732637467494061214305833071546569331846769283903364232112943347125454749708774697131756730108612477928901 593458261537716556068844745276204316308239494460406201449044676324700821725161144333810307414380993643769454376136994509520 209275090094097946999490739982969569631351330392226674241537681843493233564006268424500882264325849758919666842678891696937 841796020070577946180829229645029855800190960360250260422897310104808209564229004719623595943827863166165831239831317159051 577645371143235301157980935107653212944473520640859134537229637237839653983138503681434932845926643239361291911809411554305 3115450
e = 17
import binascii
def franklinReiter(n,e,c1,c2):
    PR.<x> = PolynomialRing(Zmod(n))
    g1 = (2*x + 3)^e - c1
    g2 = (4*x + 11)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]

m=franklinReiter(n,e,c1,c2)
print(libnum.n2s(int(m)))
# flag{r54__r3l473d_m355463_4774ck_4l50_c4ll3d_fr4nkl1n_r3173r_4774ck~}

Question 3

(NEEPUSec CTF 2021 RSA)

Description of topic:

from Crypto.Util.number import *
from sympy import nextprime
import gmpy2
import random

def encode(p1,p2,e):
    not_hint = (p1 + 1) * (p2 + 1)
    S = gmpy2.invert(e, not_hint)
    not_p = S%(p1 + 1)
    return not_p

flag = b'Neepu{********************}'
flag = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = nextprime(random. randint(1,1000))
d = gmpy2.invert(e, (p-1)*(q-1))
c = pow(flag, e, n)
print(c)
print(n)

m = encode(p, q, e)
c1 = pow(m, 7, n)
c2 = pow(m + e, 7, n)
print(c1)
print(c2)

c = 78543767285872349029076059073458316000847341792088805258173041942425687239313215276670106926320359777962661495032475004 417723103701253550583245518206305422982968675291500865382213182669036827898932991063338163290845510339896689210314509493839 746410486257998875782496654704288722251878269643040214139429715671
n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687 694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453 150572165461450371411341485911677167168492357154684642531577228543
c1 = 101860667855118297591641948032098191722249661192276686384135019966268328518928607773653716120401914779179935106684994 595451864260051819692715209813111740260879375208010440289379281205962072695078267080983796260625067458861278302797695871905 1829085903720655233948024280118985875980227528403883475592567727892
c2 = 4618210399429914556202281202343849579768607710447747263149415022203840441941410072766717129009862421411324103286112845 508660119723976108575241351962725129050947432761125359976865090833614262121000538924671450435837062923155708030151646098502 2782887233790302054696967900384601182742759555421864610431428746119

Topic Analysis:

c1 = pow(m, 7, n)
c2 = pow(m + e, 7, n)

The two strings are very familiar, but there are two unknowns, and the above two questions have only one unknown, so first find e, and then use the Franklin-Reiter related message attack to find m. How to find e, here we use Coppersmith’s short-pad attack [I haven’t seen this attack method yet, I’ll talk about it when I get to the principle], don’t say much, just go directly to the problem-solving code

def short_pad_attack(c1, c2, e, n):
    PRxy.< x, y > = PolynomialRing(Zmod(n))
    PRx.< xn > = PolynomialRing(Zmod(n))
    PRZZ.< xz, yz > = PolynomialRing(Zmod(n))
    g1 = x ^ e - c1
    g2 = (x + y) ^ e - c2
    q1 = g1. change_ring(PRZZ)
    q2 = g2. change_ring(PRZZ)
    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()
    kbits = n.nbits() // (2 * e * e)
    diff = h.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.4
    return diff


def related_message_attack(c1, c2, diff, e, n):
    PRx.< x > = PolynomialRing(Zmod(n))
    g1 = x ^ e - c1
    g2 = (x + diff) ^ e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]


if __name__ == '__main__':
    c2 = 101860667855118297591641948032098191722249661192276686384135019966268328518928607773653716120401914779179935106684994 595451864260051819692715209813111740260879375208010440289379281205962072695078267080983796260625067458861278302797695871905 1829085903720655233948024280118985875980227528403883475592567727892
    c1 = 4618210399429914556202281202343849579768607710447747263149415022203840441941410072766717129009862421411324103286112845 508660119723976108575241351962725129050947432761125359976865090833614262121000538924671450435837062923155708030151646098502 2782887233790302054696967900384601182742759555421864610431428746119
    n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687 694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453 150572165461450371411341485911677167168492357154684642531577228543
    e = 7
    diff = short_pad_attack(c1, c2, e, n)
    print("difference of two messages is %d" % diff)
    m1 = related_message_attack(c1, c2, diff, e, n)
    print("m1:", m1)
    print("m2:", m1 + diff)
  • Another way to find m (direct blasting e):
import binascii
def attack(c1, c2, n, e):
    PR.<x> = PolynomialRing(Zmod(n))
    g1 = (x)^7 - c1
    g2 = (x + e)^7 - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]
c1 = 101860667855118297591641948032098191722249661192276686384135019966268328518928607773653716120401914779179935106684994 595451864260051819692715209813111740260879375208010440289379281205962072695078267080983796260625067458861278302797695871905 1829085903720655233948024280118985875980227528403883475592567727892
c2 = 4618210399429914556202281202343849579768607710447747263149415022203840441941410072766717129009862421411324103286112845 508660119723976108575241351962725129050947432761125359976865090833614262121000538924671450435837062923155708030151646098502 2782887233790302054696967900384601182742759555421864610431428746119
n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687 694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453 150572165461450371411341485911677167168492357154684642531577228543

for e in range(1,1000):
    m = attack(c1, c2, n, e)
    try:
        if pow(m,7,n) == c1:
            print((e,m))
    except:
        pass
#Result: (71, 12925655524362509614038691625325986720665126914256550254082365415966398099455456877012993395632742360829588042575 108302297567291349420390228163587340859)
#e = 71
#m = 1292565552436250961403869162532598672066512691425655025408236541596663980994554568770129933956327423608295880425751083 02297567291349420390228163587340859
  • Find m, and m = s % (p + 1) = d % (p + 1), isn’t this similar to dp leaking, simply deduce it, and you can get p, q by replacing the addition of 1 with the subtraction of 1. Go directly to the solution code
import gmpy2
from Crypto.Util.number import *
e = 71
# m = 1292565552436250961403869162532598672066512691425655025408236541596663980994554568770129933956327423608295880425751083 02297567291349420390228163587340859
c = 78543767285872349029076059073458316000847341792088805258173041942425687239313215276670106926320359777962661495032475004 417723103701253550583245518206305422982968675291500865382213182669036827898932991063338163290845510339896689210314509493839 746410486257998875782496654704288722251878269643040214139429715671
n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687 694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453 150572165461450371411341485911677167168492357154684642531577228543
# dp = m , similar to dp
dp = 1292565552436250961403869162532598672066512691425655025408236541596663980994554568770129933956327423608295880425751083 02297567291349420390228163587340859
for i in range(1,65535):
    p = (dp*e-1)//i-1
    if n%p == 0:
        q = n//p
        d = gmpy2.invert(e, (p - 1) * (q - 1))
        flag = pow(c,d,n)
        print(long_to_bytes(flag))
        break
#Neepu{Have-a-g00d-day12138}

Harvest and experience:

I have learned a lot, mastered related message attacks, and have a more thorough understanding of reduce() and lambda() functions.
I learned another variant of the leaked dp, well, I have to say, the harvest is quite big

Just remember:

After completing NEEPUSec CTF 2023, I felt that the quality of the questions in this competition was very good, so I searched for its previous questions, and then I did the NEEPUSec CTF 2021 RSA question. At first, it seemed very simple to read its title description, but after pushing it back and forth, I could only get m * e = 1 % (p + 1), m and e were still unknown, and as a result, nothing was found. After reading wp, I know that there are specific knowledge points for solving m and e here, so I searched a lot of information, and finally figured out this question.

In fact, at the beginning, it was based on the idea of directly setting the script, but suddenly thought of a sentence said by a senior, “We are engaged in network security, not looking for ctfer of flag, don’t reverse the two.”
But in fact, it is still a bit reluctant to fully understand this question. There are some small points in it that I still don’t understand. Filling attack (haven’t looked for information yet), in short, the general steps and meaning are clear.