Skip to content

Latest commit

 

History

History

hastad

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 

Hastad (crypto 400)

###ENG PL

In the task we get the same unpadded message encrypted via RSA using 3 different public keys, but with the same exponent e = 3. This means we can utilize Hastad Broadcast Attack here to recover the message thanks to Chinese Reminder Theorem.

The public exponent is 3 in all cases so what we have is in fact:

m^e = y1 mod n1
m^e = y2 mod n2
m^e = y3 mod n3

From Chinese Reminder Theorem we know it's possible to recover m^e, and once we have it, we only need to get k-th integer root to get the flag:

from src.crypto_commons.generic import long_to_bytes
from src.crypto_commons.rsa.rsa_commons import hastad_broadcast


def main():
    n1 = 95118357989037539883272168746004652872958890562445814301889866663072352421703264985997800660075311645555799745426868343365321502734736006248007902409628540578635925559742217480797487130202747020211452620743021097565113059392504472785227154824117231077844444672393221838192941390309312484066647007469668558141
    n2 = 98364165919251246243846667323542318022804234833677924161175733253689581393607346667895298253718184273532268982060905629399628154981918712070241451494491161470827737146176316011843738943427121602324208773653180782732999422869439588198318422451697920640563880777385577064913983202033744281727004289781821019463
    n3 = 68827940939353189613090392226898155021742772897822438483545021944215812146809318686510375724064888705296373853398955093076663323001380047857809774866390083434272781362447147441422207967577323769812896038816586757242130224524828935043187315579523412439309138816335569845470021720847405857361000537204746060031
    c1 = 64830446708169012766414587327568812421130434817526089146190136796461298592071238930384707543318390292451118980302805512151790248989622269362958718228298427212630272525186478627299999847489018400624400671876697708952447638990802345587381905407236935494271436960764899006430941507608152322588169896193268212007
    c2 = 96907490717344346588432491603722312694208660334282964234487687654593984714144825656198180777872327279250667961465169799267405734431675111035362089729249995027326863099262522421206459400405230377631141132882997336829218810171728925087535674907455584557956801831447125486753515868079342148815961792481779375529
    c3 = 43683874913011746530056103145445250281307732634045437486524605104639785469050499171640521477036470750903341523336599602288176611160637522568868391237689241446392699321910723235061180826945464649780373301028139049288881578234840739545000338202917678008269794179100732341269448362920924719338148857398181962112
    print(long_to_bytes(hastad_broadcast([(c1, n1), (c2, n2), (c3, n3)])))


main()

Using some functions from our crypto-commons:

def solve_crt(residue_and_moduli):
    """
    Solve CRT for given modular residues and modulus values, eg:
    x = 1 mod 3
    x = 2 mod 4
    x = 3 mod 5
    x = 58
    residue_and_moduli = [(1,3), (2,4), (3,5)]
    :param residue_and_moduli: list of pairs with (modular residue mod n, n)
    :return: x
    """
    moduli = [x[1] for x in residue_and_moduli]
    residues = [x[0] for x in residue_and_moduli]
    N = reduce(lambda x, y: x * y, moduli)
    Nxs = [N / n for n in moduli]
    ds = [modinv(N / n, n) for n in moduli]
    mults = [residues[i] * Nxs[i] * ds[i] for i in range(len(moduli))]
    return reduce(lambda x, y: x + y, mults) % N

def hastad_broadcast(residue_and_moduli):
    """
    Hastad RSA attack for the same message encrypted with the same public exponent e and different modulus.
    Requires exactly 'e' pairs as input
    :param residue_and_moduli: list of pairs (residue, modulus)
    :return: decrypted message
    """
    import gmpy2
    k = len(residue_and_moduli)
    solution, _ = gmpy2.iroot(solve_crt(residue_and_moduli), k)
    assert residue_and_moduli[0][0] == pow(int(solution), k, residue_and_moduli[0][1])
    return solution

And this gives the flag: theoretical_computer_scientist_johan_torkel_hastad

###PL version

W zadaniu mamy do czynienia z wiadomością szyfrowaną za pomocą RSA bez paddingu przy użyciu 3 różnych kluczy, ale z tym samym wykładnikiem e = 3. To oznacza że możemy użyć Hastad Broadcast Attack aby odzyskać wiadomość za pomocą Chińskiego Twierdzenia o Resztach.

Wykładnik dla wszystkich 3 szyfrogramów wynosi 3 więc mamy:

m^e = y1 mod n1
m^e = y2 mod n2
m^e = y3 mod n3

Z Chińskiego Twierdzenia o Resztach wiemy że można odzyskać z takiego układu m^e, a wtedy potrzebujemy już tylko wyliczyć k-ty pierwiastek całkowity aby dostać flagę:

from src.crypto_commons.generic import long_to_bytes
from src.crypto_commons.rsa.rsa_commons import hastad_broadcast


def main():
    n1 = 95118357989037539883272168746004652872958890562445814301889866663072352421703264985997800660075311645555799745426868343365321502734736006248007902409628540578635925559742217480797487130202747020211452620743021097565113059392504472785227154824117231077844444672393221838192941390309312484066647007469668558141
    n2 = 98364165919251246243846667323542318022804234833677924161175733253689581393607346667895298253718184273532268982060905629399628154981918712070241451494491161470827737146176316011843738943427121602324208773653180782732999422869439588198318422451697920640563880777385577064913983202033744281727004289781821019463
    n3 = 68827940939353189613090392226898155021742772897822438483545021944215812146809318686510375724064888705296373853398955093076663323001380047857809774866390083434272781362447147441422207967577323769812896038816586757242130224524828935043187315579523412439309138816335569845470021720847405857361000537204746060031
    c1 = 64830446708169012766414587327568812421130434817526089146190136796461298592071238930384707543318390292451118980302805512151790248989622269362958718228298427212630272525186478627299999847489018400624400671876697708952447638990802345587381905407236935494271436960764899006430941507608152322588169896193268212007
    c2 = 96907490717344346588432491603722312694208660334282964234487687654593984714144825656198180777872327279250667961465169799267405734431675111035362089729249995027326863099262522421206459400405230377631141132882997336829218810171728925087535674907455584557956801831447125486753515868079342148815961792481779375529
    c3 = 43683874913011746530056103145445250281307732634045437486524605104639785469050499171640521477036470750903341523336599602288176611160637522568868391237689241446392699321910723235061180826945464649780373301028139049288881578234840739545000338202917678008269794179100732341269448362920924719338148857398181962112
    print(long_to_bytes(hastad_broadcast([(c1, n1), (c2, n2), (c3, n3)])))


main()

Używając kilku funkcji z naszych crypto-commons:

def solve_crt(residue_and_moduli):
    """
    Solve CRT for given modular residues and modulus values, eg:
    x = 1 mod 3
    x = 2 mod 4
    x = 3 mod 5
    x = 58
    residue_and_moduli = [(1,3), (2,4), (3,5)]
    :param residue_and_moduli: list of pairs with (modular residue mod n, n)
    :return: x
    """
    moduli = [x[1] for x in residue_and_moduli]
    residues = [x[0] for x in residue_and_moduli]
    N = reduce(lambda x, y: x * y, moduli)
    Nxs = [N / n for n in moduli]
    ds = [modinv(N / n, n) for n in moduli]
    mults = [residues[i] * Nxs[i] * ds[i] for i in range(len(moduli))]
    return reduce(lambda x, y: x + y, mults) % N

def hastad_broadcast(residue_and_moduli):
    """
    Hastad RSA attack for the same message encrypted with the same public exponent e and different modulus.
    Requires exactly 'e' pairs as input
    :param residue_and_moduli: list of pairs (residue, modulus)
    :return: decrypted message
    """
    import gmpy2
    k = len(residue_and_moduli)
    solution, _ = gmpy2.iroot(solve_crt(residue_and_moduli), k)
    assert residue_and_moduli[0][0] == pow(int(solution), k, residue_and_moduli[0][1])
    return solution

Co daje flagę: theoretical_computer_scientist_johan_torkel_hastad