#**Quadratic Residues**
-Chúng ta cần tìm một số nguyên a sao cho a^2 ≡ x (mod p), trong đó p là một số nguyên tố dương, x là một số nguyên và a là một phần tử của trường số nguyên modulo p (Fp).
-Với bài này, p=29 và x là 1 trong các số ints = [14, 6, 11]. Ta cần tìm a sao cho a^2 ≡ x (mod 29).
-Hướng làm: thử lần lượt a trong Fp xem phần tử nào thỏa mãn.
-Thuật ngữ: Thặng dư bậc 2. x là thặng dư bậc 2 nếu tồn tại a sao cho a^2 ≡ x (mod p)
-Điều kiện cần và đủ x là thặng dư bậc 2 của p:
*x^((p-1)/2) ≡ 1(mod p)*

#**Legendre Symbol**
Bài này cần tìm căn bậc 2 của một thặng dư bậc 2 ta chia làm 2 bước:
-Tìm thặng dư bậc 2 trong ints, áp dụng điều kiện:
*a^((p-1)/2) ≡ 1(mod p)*
-Tính căn bậc 2 của một thặng dư bậc 2 bằng công thức:
*a^((p+1)/4) mod p* (để chắc chắn số đó nằm trong Fp)
Chứng minh:

#**Chinese Remainder Theorem**
Định lý dư Trung Hoa cung cấp một giải pháp duy nhất cho một tập hợp các phương trình đồng dư tuyến tính nếu các mô đun của chúng là số nguyên tố.

Điều này có nghĩa là, với một tập hợp các số nguyên tùy ý a và các số nguyên tố n sao cho:
x ≡ a1 mod n1
x ≡ a2 mod n2
...
x ≡ an mod nn
Thì sẽ tồn tại x sao cho x ≡ a (mod N) với N = n1*n2*...*nn
Ta thường sử dụng Định lý dư Trung Hoa để giúp chúng ta giảm bài toán của các số nguyên lớn thành một tập các bài toán dễ dàng hơn.
a = ∑ ai*mi*Ni với Ni=N/ni

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extended_gcd(b % a, a)
        return g, x - (b // a) * y, y

def crt(n, a):
    N = 1
    for ni in n:
        N *= ni
    result = 0
    for ni, ai in zip(n, a):
        Ni = N // ni
        _, mi, _ = extended_gcd(Ni, ni) # _ là những giá trị ta không dùng đến, mi Là nghịch đảo modulo của Ni so với ni
        result += ai * mi * Ni
    return result % N

n = [5, 11, 17]
a = [2, 3, 5]

A = crt(n, a)
print("a =", A)

#**Adrien's Signs**
Trong bài toán "Adrien's Signs", chúng ta được cho một tập hợp các số nguyên và được yêu cầu phải giải mã chúng để thu được thông điệp gốc.
Cách mã hóa: Adrien chia thông điệp thành các bit.
Đối với mỗi bit: Nếu bit là 1, Adrien chọn một số a sao cho a là một quadratic residue modulo p.
Nếu bit là 0, Adrien chọn -a.
Cách giải mã: Kiểm tra xem a có phải quadratic residue modulo p không, nếu đúng thì ta biết bit tương ứng là 1, ngược lại là 0.

from Crypto.Util.number import long_to_bytes
p= 1007621497415251

data = [67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 352175210511707, 306237700811584, 631393408838583, 589243747914057, 538776819034934, 365364592128161, 454970171810424, 986711310037393, 657756453404881, 388329936724352, 90991447679370, 714742162831112, 62293519842555, 653941126489711, 448552658212336, 970169071154259, 339472870407614, 406225588145372, 205721593331090, 926225022409823, 904451547059845, 789074084078342, 886420071481685, 796827329208633, 433047156347276, 21271315846750, 719248860593631, 534059295222748, 879864647580512, 918055794962142, 635545050939893, 319549343320339, 93008646178282, 926080110625306, 385476640825005, 483740420173050, 866208659796189, 883359067574584, 913405110264883, 898864873510337, 208598541987988, 23412800024088, 911541450703474, 57446699305445, 513296484586451, 180356843554043, 756391301483653, 823695939808936, 452898981558365, 383286682802447, 381394258915860, 385482809649632, 357950424436020, 212891024562585, 906036654538589, 706766032862393, 500658491083279, 134746243085697, 240386541491998, 850341345692155, 826490944132718, 329513332018620, 41046816597282, 396581286424992, 488863267297267, 92023040998362, 529684488438507, 925328511390026, 524897846090435, 413156582909097, 840524616502482, 325719016994120, 402494835113608, 145033960690364, 43932113323388, 683561775499473, 434510534220939, 92584300328516, 763767269974656, 289837041593468, 11468527450938, 628247946152943, 8844724571683, 813851806959975, 72001988637120, 875394575395153, 70667866716476, 75304931994100, 226809172374264, 767059176444181, 45462007920789, 472607315695803, 325973946551448, 64200767729194, 534886246409921, 950408390792175, 492288777130394, 226746605380806, 944479111810431, 776057001143579, 658971626589122, 231918349590349, 699710172246548, 122457405264610, 643115611310737, 999072890586878, 203230862786955, 348112034218733, 240143417330886, 927148962961842, 661569511006072, 190334725550806, 763365444730995, 516228913786395, 846501182194443, 741210200995504, 511935604454925, 687689993302203, 631038090127480, 961606522916414, 138550017953034, 932105540686829, 215285284639233, 772628158955819, 496858298527292, 730971468815108, 896733219370353, 967083685727881, 607660822695530, 650953466617730, 133773994258132, 623283311953090, 436380836970128, 237114930094468, 115451711811481, 674593269112948, 140400921371770, 659335660634071, 536749311958781, 854645598266824, 303305169095255, 91430489108219, 573739385205188, 400604977158702, 728593782212529, 807432219147040, 893541884126828, 183964371201281, 422680633277230, 218817645778789, 313025293025224, 657253930848472, 747562211812373, 83456701182914, 470417289614736, 641146659305859, 468130225316006, 46960547227850, 875638267674897, 662661765336441, 186533085001285, 743250648436106, 451414956181714, 527954145201673, 922589993405001, 242119479617901, 865476357142231, 988987578447349, 430198555146088, 477890180119931, 844464003254807, 503374203275928, 775374254241792, 346653210679737, 789242808338116, 48503976498612, 604300186163323, 475930096252359, 860836853339514, 994513691290102, 591343659366796, 944852018048514, 82396968629164, 152776642436549, 916070996204621, 305574094667054, 981194179562189, 126174175810273, 55636640522694, 44670495393401, 74724541586529, 988608465654705, 870533906709633, 374564052429787, 486493568142979, 469485372072295, 221153171135022, 289713227465073, 952450431038075, 107298466441025, 938262809228861, 253919870663003, 835790485199226, 655456538877798, 595464842927075, 191621819564547]
result = ""
for x in data:
    c = pow(x, (p-1)//2, p)
    if c == 1:
        result += "1"
    else:
        result += "0"

print(long_to_bytes(int(result, 2)).decode())

Hàm int(res, 2) được sử dụng để chuyển chuỗi res sang giá trị số nguyên dựa trên hệ cơ số 2. Trong trường hợp này, chuỗi res chứa các ký tự '0' và '1', đại diện cho các bit của một số nguyên. Bằng cách sử dụng hệ cơ số 2, chúng ta có thể biểu diễn số nguyên từ các bit này.

#**Modular Binomials**
N = p*q
c1 = (2*p + 3*q)**e1 mod N
c2 = (5*p + 7*q)**e2 mod N
Bài này cần tính p,q

from math import gcd
N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

d = pow(5,(-e2 * e1),N) * pow(c2, e1, N) - pow(2, (-e1 * e2), N) * pow(c1, e2, N)
q = gcd(d, N)
p = N // q

print('crypto{{{},{}}}'.format(p, q))


#**Crypto01**
Cách mã hóa:
-Chuyển flag thành dạng nhị phân
-Với mỗi bit trong flag, ta sẽ lấy a^(ngẫu nhiên+(0 hoặc 1))mod p, kết quả sữ được thêm vào dãy encrypt.
Cách giải mã: (làm hơi thủ công và mất thời gian)
-Ta có dãy encrypt
pow(a,x,p)=encrypt
x = (randint(2, p) * randrange(2, p, 2)) + int(bit)
= chẵn + int(bit)
Áp dụng thêm nếu x chẵn thì encrypt chẵn và ngược lại.
Từ đó nếu encrypt chẵn thì bit=0 và ngược lại thì bit=1.
-Khi ta được dãy decrypt dạng nhị phân, ta sẽ chuyển sang byte rồi decode.

(Bài vẫn đang sai :) )

from Crypto.Util.number import long_to_bytes

a = 1337
p = 96517490730367252566551196176049957092195411726055764912412605750547823858339
encrypt = ...

decrypted_binary = ''.join([str(i % 2) for i in encrypt])
print(decrypted_binary)
# Chuyển đổi dạng nhị phân thành số nguyên.
decrypted_integer = int(decrypted_binary, 2)
print(decrypted_integer)
# Chuyển đổi số nguyên thành dạng byte và sau đó giải mã ra từ byte.
decrypted_flag = long_to_bytes(decrypted_integer)
print(decrypted_flag)
# In ra flag đã giải mã.
# print(decrypted_flag.decode())