Skip to content

Legend

Description

Write Up: Tyron
Créateur: Yogosha
Difficulté: facile
Points: 150
Format du flag: PPC2024{flag}

Enoncé

  • Français: Nous fournissons notre chiffrement pour le système de points secrets de MegaCorp, nous pensons que tout est sécurisé, pouvez-vous essayer ?
  • English: We provide our encryption for MegaCorp's secret points system, we think it's all secure, can you give it a try?

Pièce(s) jointe(s):

Solution détaillée

player.py 
from random import randint

a = 288260533169915
p = 1007621497415251

FLAG = b"PPC2024{REDACTED}"


def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag]) # chaque caractère to binaire
    for b in plaintext:
        e = randint(1, p)
        n = pow(a, e, p)
        if b == '1':
            ciphertext.append(n)
        else:
            n = -n % p
            ciphertext.append(n)
    return ciphertext


print(encrypt_flag(FLAG))

'''
    [828385226842191, 884750330806283, 388570376230914, 205778797108144, 638369485764265, 69553132238148, 914460818501558, 13379099491480, 413346006831117, 741990430872996, 404039335154972, 337032981465603, 813973495213166, 849525080960656, 469174126189644, 454412813601180, 224421703708509, 312511174463140, 361563200570126, 847258418044783, 162086149759169, 381850173544007, 197363232503970, 845828471250686, 106660093241302, 947502641559183, 315391286945203, 450457288568455, 892168892661339, 948435665125264, 239805296072908, 544476170770024, 819902082919125, 539069227549429, 540656081002047, 331630242769344, 664716916353105, 244752846739769, 819038499760649, 78470407305005, 317015896320788, 772740995468290, 558472131576413, 563751162082506, 66131311572166, 495470153223431, 453455959350407, 812416491005115, 212301471971528, 1001728315460707, 360182719076079, 403131883381677, 212096731053902, 315118136060712, 38703242475581, 904284254966929, 123025326268469, 53773098486664, 651530957443841, 73799825375654, 990445098510197, 872146702664040, 533382695643271, 683138683037949, 221226605405410, 20318989875754, 153638102855200, 553781554977906, 962377297451780, 509279211769760, 591168720293735, 916600918386333, 675052877320757, 611448601932642, 861298336449398, 675758433888843, 567236338543871, 194562492980741, 753962336111480, 942900772057946, 527383061956393, 886878317000835, 738951041753626, 44079826078335, 705912019707333, 613504834174280, 426753983673881, 158254296021228, 925240206539261, 445845549405730, 333581201702230, 278659615053609, 71593005652192, 439519132324054, 84664430167409, 619229613229618, 696678989147946, 501941148845726, 125793184976446, 310783557359522, 900188720208438, 81956682753876, 822734158955703, 749169043596199, 847258212995182, 429799246097054, 922539937592645, 892180612498511, 201050027693215, 605295024001706, 340116423010122, 864152875089762, 875246480087219, 846788671570737, 156127780686744, 426857113953329, 813647847792868, 750885942922158, 483654113690232, 705769576241822, 704037794995886, 595670251761290, 460047193028596, 60267611451148, 729026604258752, 955862092867721, 649013949112319, 99731746970076, 962655632565009, 862315496302689, 894631209776222, 60616076696180, 61636549669898, 132275476007143, 397062636321012, 391042343948712, 652407418227371, 41784745558361, 440160938480014, 887339419649672, 231158422246203, 744801114788651, 803151388477335, 966379522368877, 857392667751251, 677775640693699, 420221354559703, 897414273163298, 110416417065392, 192000016421537, 252036767375257, 731057157140649, 8925182150751, 189898494578180, 184286771933789, 794384054994436, 399657459187255, 842625003035788, 950266212513231, 338194429031718, 722742388283523, 925408068530869, 24646943304551, 73238636644961, 616930400333127, 187081361951157, 248019083721065, 251157441712705, 804702148212411, 505525909601862, 34414520827564, 477455633131130, 426992447741910, 709019745087039, 258854132367952, 842927628930359, 131285629402068, 510974599417228, 789632741612521, 885251829020685, 435708837785478, 428099314696031, 186546641692708, 821278660764656, 962423218529295, 628355072214389, 367582360674662, 770035005833105, 133988077113241, 938708027986090, 147527088740717, 363893058407270, 915715055205114, 428717951140847, 302121462874300, 193699709418485, 375961454982136, 809826176809785, 89863346252234, 71706561241191, 974009468772679, 473200886829824, 221557310112488, 342897908810582, 217512190895301, 796785920906820, 40469251248088, 426078253285341, 16222086473744, 646482470054426, 692824995159910, 587814176266800, 427387397818853, 921630362114332, 649035217466289, 218051970393608, 470302751708131, 880281936801962, 350096517731954, 241359150225626, 836193267072137, 107539075393329, 138104764093741, 674632839526888, 804696787629961, 640805046781299, 963470988829567, 50821721702212, 643969147535178, 631762494747104, 60176507269066, 733015588136338, 78624201754536, 15708594773324, 403448455423321, 508551344914849, 750688474426581, 795481489053587, 853152575969425, 917476993113167, 83807873375891, 964300249453063, 266711214861811, 1000361881119009, 232177426323349, 97716719767841, 665413222785511, 234108433674735, 68687047057345, 625433668759702, 873128553138350, 942502721284303, 165886284006184, 299851912084940, 273163860732884, 918910288014889]
'''

Le programme est simple :

  • Convertit le flag en binaire
  • Par court chaque bit:
    • si le bit vaut 1, $ a^{e} \equiv n \mod p $ est stocké dans le ciphertext
    • si le bit vaut 0, $ -n \equiv n \mod p $ est stocké dans le ciphertext

On va s'intéresser plus en détail sur les calculs effectués et les nombres choisis notamment a et p :

On a :

  • $ a = 288260533169915 $ (non premier)
  • $ p = 1007621497415251 $ (premier )
  • $ e = randint(1, p) $

qui servent à générer une valeur n : $ n = a^{e} \mod p $

A ce moment là on peut tenter de savoir quels point commun il y a entre les valeurs résultant de $ n = a^{e} \mod p $ ou de $ -n \mod p$.

En sachant que n est le résultat d'une exponentiation modulaire (c'est a dire un nombre élevé à une certaine puissance puis réduit modulo p), on peut définir que n est un résidu quadratique.

On remarquera qu'un résidu quadratique ne concerne que le nombre élévés au carré mais ca marche aussi avec les autres puissances.

Pour savoir si un nombre est résidu quadratique, on utilise le symbole de légendre. Pour faire court on calcule $ n^{\frac{p-1}{2}} \mod p $ :

  • si on obtient $ 1 \mod p $, c'est un résidu quadratique
  • si on obtient $ -1 \mod p = p-1 \mod p$, c'est un résidu non-quadratique

On peut tester ca avec ce bout de code :

from random import randint

a = 288260533169915
p = 1007621497415251

for i in range(10):
    e = randint(1, p)
    n = pow(a, e, p)

    print(pow(n, (p-1)//2, p))

Qui renvoie uniquement des 1, ce qui signifie qu'à la base n est un résidu qudratique. Et si on le met au négatif comme dans le script tu challenge, après application du symbole de l"gendre on obtient $ -1 \mod p $.

On peut écrire : $ n^{\frac{p-1}{2}} \equiv 1 \mod p $.

Alors : $ (-n)^{\frac{p-1}{2}} \equiv -1 \equiv p - 1 \equiv 1007621497415250 \mod p $

On sait maintenant comment savoir si un une valeur dans la liste correspond à un 1 ou un 0.

solve.py 
output = [828385226842191, 884750330806283, 388570376230914, 205778797108144, 638369485764265, 69553132238148, 914460818501558, 13379099491480, 413346006831117, 741990430872996, 404039335154972, 337032981465603, 813973495213166, 849525080960656, 469174126189644, 454412813601180, 224421703708509, 312511174463140, 361563200570126, 847258418044783, 162086149759169, 381850173544007, 197363232503970, 845828471250686, 106660093241302, 947502641559183, 315391286945203, 450457288568455, 892168892661339, 948435665125264, 239805296072908, 544476170770024, 819902082919125, 539069227549429, 540656081002047, 331630242769344, 664716916353105, 244752846739769, 819038499760649, 78470407305005, 317015896320788, 772740995468290, 558472131576413, 563751162082506, 66131311572166, 495470153223431, 453455959350407, 812416491005115, 212301471971528, 1001728315460707, 360182719076079, 403131883381677, 212096731053902, 315118136060712, 38703242475581, 904284254966929, 123025326268469, 53773098486664, 651530957443841, 73799825375654, 990445098510197, 872146702664040, 533382695643271, 683138683037949, 221226605405410, 20318989875754, 153638102855200, 553781554977906, 962377297451780, 509279211769760, 591168720293735, 916600918386333, 675052877320757, 611448601932642, 861298336449398, 675758433888843, 567236338543871, 194562492980741, 753962336111480, 942900772057946, 527383061956393, 886878317000835, 738951041753626, 44079826078335, 705912019707333, 613504834174280, 426753983673881, 158254296021228, 925240206539261, 445845549405730, 333581201702230, 278659615053609, 71593005652192, 439519132324054, 84664430167409, 619229613229618, 696678989147946, 501941148845726, 125793184976446, 310783557359522, 900188720208438, 81956682753876, 822734158955703, 749169043596199, 847258212995182, 429799246097054, 922539937592645, 892180612498511, 201050027693215, 605295024001706, 340116423010122, 864152875089762, 875246480087219, 846788671570737, 156127780686744, 426857113953329, 813647847792868, 750885942922158, 483654113690232, 705769576241822, 704037794995886, 595670251761290, 460047193028596, 60267611451148, 729026604258752, 955862092867721, 649013949112319, 99731746970076, 962655632565009, 862315496302689, 894631209776222, 60616076696180, 61636549669898, 132275476007143, 397062636321012, 391042343948712, 652407418227371, 41784745558361, 440160938480014, 887339419649672, 231158422246203, 744801114788651, 803151388477335, 966379522368877, 857392667751251, 677775640693699, 420221354559703, 897414273163298, 110416417065392, 192000016421537, 252036767375257, 731057157140649, 8925182150751, 189898494578180, 184286771933789, 794384054994436, 399657459187255, 842625003035788, 950266212513231, 338194429031718, 722742388283523, 925408068530869, 24646943304551, 73238636644961, 616930400333127, 187081361951157, 248019083721065, 251157441712705, 804702148212411, 505525909601862, 34414520827564, 477455633131130, 426992447741910, 709019745087039, 258854132367952, 842927628930359, 131285629402068, 510974599417228, 789632741612521, 885251829020685, 435708837785478, 428099314696031, 186546641692708, 821278660764656, 962423218529295, 628355072214389, 367582360674662, 770035005833105, 133988077113241, 938708027986090, 147527088740717, 363893058407270, 915715055205114, 428717951140847, 302121462874300, 193699709418485, 375961454982136, 809826176809785, 89863346252234, 71706561241191, 974009468772679, 473200886829824, 221557310112488, 342897908810582, 217512190895301, 796785920906820, 40469251248088, 426078253285341, 16222086473744, 646482470054426, 692824995159910, 587814176266800, 427387397818853, 921630362114332, 649035217466289, 218051970393608, 470302751708131, 880281936801962, 350096517731954, 241359150225626, 836193267072137, 107539075393329, 138104764093741, 674632839526888, 804696787629961, 640805046781299, 963470988829567, 50821721702212, 643969147535178, 631762494747104, 60176507269066, 733015588136338, 78624201754536, 15708594773324, 403448455423321, 508551344914849, 750688474426581, 795481489053587, 853152575969425, 917476993113167, 83807873375891, 964300249453063, 266711214861811, 1000361881119009, 232177426323349, 97716719767841, 665413222785511, 234108433674735, 68687047057345, 625433668759702, 873128553138350, 942502721284303, 165886284006184, 299851912084940, 273163860732884, 918910288014889]

for v in output :
    if pow(v, (p-1)//2, p) == 1:
        recovered+="1"
    else:
        recovered+="0"

recovered_bits = [recovered[i:i+8] for i in range(0, len(recovered), 8)]
print(''.join([chr(int(c, 2)) for c in recovered_bits]))

FLAG : PPC2024{legendre_symbol?...}

Retex

Ce fut un manière sympathique de me rappeler les bases en arithmétique modulaire.

Lien(s) utile(s)