writeups

ABCTF - 125 - A Small Broadcast - Cryptography

noraj (Alexandre ZANNI)
, , ,
🇬🇧

Information#

Version#

By Translated by Version Comment
Chill3d noraj 1.0 Creation

CTF#

  • Name : ABCTF 2016
  • Website : http://abctf.xyz/
  • Type : Online
  • Format : Jeopardy - Student
  • CTF Time : link

Description#

I RSA encrypted the same message 3 different times with the same exponent. Can you decrypt this?

Solution#

Corrected challenge version URL:

1
2
3
4
5
6
7
8
9
10
11
Problem updated on 7/17/16 @ 8PM EST - fixed values
I RSA encrypted the same message 3 different times with the same exponent. Can you decrypt it?

N1:79608037716527910392060670707842954224114341083822168077002144855358998405023007345791355970838437273653492726857398313047195654933011803740498167538754807659255275632647165202835846338059572102420992692073303341392512490988413552501419357400503232190597741120726276250753866130679586474440949586692852365179
C1:34217065803425349356447652842993191079705593197469002356250751196039765990549766822180265723173964726087016890980051189787233837925650902081362222218365748633591895514369317316450142279676583079298758397507023942377316646300547978234729578678310028626408502085957725408232168284955403531891866121828640919987

N2:58002222048141232855465758799795991260844167004589249261667816662245991955274977287082142794911572989261856156040536668553365838145271642812811609687362700843661481653274617983708937827484947856793885821586285570844274545385852401777678956217807768608457322329935290042362221502367207511491516411517438589637
C2:48038542572368143315928949857213341349144690234757944150458420344577988496364306227393161112939226347074838727793761695978722074486902525121712796142366962172291716190060386128524977245133260307337691820789978610313893799675837391244062170879810270336080741790927340336486568319993335039457684586195656124176

N3:95136786745520478217269528603148282473715660891325372806774750455600642337159386952455144391867750492077191823630711097423473530235172124790951314315271310542765846789908387211336846556241994561268538528319743374290789112373774893547676601690882211706889553455962720218486395519200617695951617114702861810811
C3:55139001168534905791033093049281485849516290567638780139733282880064346293967470884523842813679361232423330290836063248352131025995684341143337417237119663347561882637003640064860966432102780676449991773140407055863369179692136108534952624411669691799286623699981636439331427079183234388844722074263884842748
  1. The idea is to carry out a Håstad's broadcast attack on the RSA protocol. This attack will allow us to decipher a text transmitted multiple times, provided that the exponent of the key that was used to cipher this text be lower or equal to the number of obtained transmissions.
  2. So, here, exponent must be 1, 2 or 3 (it's often 3).
  3. Here is the script (comments are in French):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# RSA : Hastad Attack
# Chill3d
import os
def eea(a,b):
    """Extended Euclidean Algorithm for GCD"""
    v1 = [a,1,0]
    v2 = [b,0,1]
    while v2[0]<>0:
       p = v1[0]//v2[0] # floor division
       v2, v1 = map(lambda x, y: x-y,v1,[p*vi for vi in v2]), v2
    return v1

def inverse(m,k):
     """
     Retourne b de maniere que b*m mod k = 1, ou 0 s'il n'y a pas de solution
     """
     v = eea(m,k)
     return (v[0]==1)*(v[1] % k)

def crt(N,e):
     """
     Theoreme des reste chinois:
     N = Liste des modulo des clefs publiques
     e = Exposant des clefs publiques

     Chinese Remainder Theorem:
     ms = list of pairwise relatively prime integers
     as = remainders when x is divided by ms
     (ai is 'each in as', mi 'each in ms')

     The solution for x modulo M (M = product of ms) will be:
     x = a1*M1*y1 + a2*M2*y2 + ... + ar*Mr*yr (mod M),
     where Mi = M/mi and yi = (Mi)^-1 (mod mi) for 1 <= i <= r.
     """

     M  = reduce(lambda x, y: x*y,N)        # Multiplication des N ; multiply N together
     Ms = [M/mi for mi in N]   # Liste de tous les M/N list of all M/mi
     ys = [inverse(Mi, mi) for Mi,mi in zip(Ms,N)] # Utilise l'inverse,eea ; uses inverse,eea
     return reduce(lambda x, y: x+y,[ai*Mi*yi for ai,Mi,yi in zip(e,Ms,ys)]) % M

def root(x,n):
    """
    Fait une racine d'ordre n sur le nombre x

    Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

#Exposant commun aux 3 messages
e=3
#Modulo des cles publiques
N=[79608037716527910392060670707842954224114341083822168077002144855358998405023007345791355970838437273653492726857398313047195654933011803740498167538754807659255275632647165202835846338059572102420992692073303341392512490988413552501419357400503232190597741120726276250753866130679586474440949586692852365179,
58002222048141232855465758799795991260844167004589249261667816662245991955274977287082142794911572989261856156040536668553365838145271642812811609687362700843661481653274617983708937827484947856793885821586285570844274545385852401777678956217807768608457322329935290042362221502367207511491516411517438589637,
95136786745520478217269528603148282473715660891325372806774750455600642337159386952455144391867750492077191823630711097423473530235172124790951314315271310542765846789908387211336846556241994561268538528319743374290789112373774893547676601690882211706889553455962720218486395519200617695951617114702861810811]
#Messages communiques avec la meme cle privee
y=[34217065803425349356447652842993191079705593197469002356250751196039765990549766822180265723173964726087016890980051189787233837925650902081362222218365748633591895514369317316450142279676583079298758397507023942377316646300547978234729578678310028626408502085957725408232168284955403531891866121828640919987,
48038542572368143315928949857213341349144690234757944150458420344577988496364306227393161112939226347074838727793761695978722074486902525121712796142366962172291716190060386128524977245133260307337691820789978610313893799675837391244062170879810270336080741790927340336486568319993335039457684586195656124176,
55139001168534905791033093049281485849516290567638780139733282880064346293967470884523842813679361232423330290836063248352131025995684341143337417237119663347561882637003640064860966432102780676449991773140407055863369179692136108534952624411669691799286623699981636439331427079183234388844722074263884842748]
#On applique le theoreme des restes Chinois sur N et y
F=crt(N,y)
print "F",F
#On fait une racine cubique de F
intflag = root(F,e)
print "intflag",intflag
#On affiche sa valeur
flag = hex(intflag)[2:-1].decode('hex')
print flag
Share