babySPN
K = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0]
给了k，按照代码逻辑直接跑，非预期。
K = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0]
hash_value = sha256(long_to_bytes(list_to_int(K))).hexdigest()
print(hash_value)
babySPN revenge
中间相遇攻击，round_func是线性的，可以反推，正向跑两轮需要知道key的前20bit，由于enc中的
for i in range(16):
Y[i] ^= K[kstart+i]
函数，逆向跑两轮需要key的后24bit，先跑出正向两轮的所有结果，再跑逆向两轮，如果与正向相同，则输出。
from hashlib import sha256
from Crypto.Util.number import long_to_bytes
from tqdm import tqdm
def bin_to_list(r, bit_len):
list = [r >> d & 1 for d in range(bit_len)][::-1]
return list
def list_to_int(list):
return int("".join(str(i) for i in list), 2)
Pbox=[1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]
Sbox=[14, 13, 11, 0, 2, 1, 4, 15, 7, 10, 8, 5, 9, 12, 3, 6]
def round_func(X,r,K):
kstart=4*r - 4
XX = [0] * 16
for i in range(16):
XX[i] = X[i] ^ K[kstart+i]
for i in range(4):
value = list_to_int(XX[4*i:4*i+4])
s_value = Sbox[value]
s_list = bin_to_list(s_value, 4)
XX[4*i],XX[4*i+1],XX[4*i+2],XX[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]
Y=[0] * 16
for i in range(16):
Y[Pbox[i]-1]=XX[i]
return Y
def enc(X,K):
Y = round_func(X,1,K)
Y = round_func(Y,2,K)
# Y = round_func(Y,3,K)
# Y = round_func(Y,4,K)
#
# kstart=4*5 - 4
# for i in range(16):
# Y[i] ^= K[kstart+i]
return Y
def re_round_func(Y,r,K):
XX = [0]*16
for i in range(16):
XX[i] = Y[Pbox[i]-1]
for i in range(4):
value = list_to_int(XX[4 * i:4 * i + 4])
s_value = Sbox.index(value)
s_list = bin_to_list(s_value, 4)
XX[4 * i], XX[4 * i + 1], XX[4 * i + 2], XX[4 * i + 3] = s_list[0], s_list[1], s_list[2], s_list[3]
kstart = 4 * r - 4
X = [0] * 16
for i in range(16):
X[i] = XX[i] ^ K[kstart+i]
return X
x1,x2,x3,x4 = [0]*16,[0]*16,[0]*16,[0]*16
x1[0],x2[4],x3[8],x4[12] = 1,1,1,1
forward = set()
for i in tqdm(range(2**20)):
K0 = bin_to_list(i,20)
CC1,CC2,CC3,CC4 = enc(x1,K0),enc(x2,K0),enc(x3,K0),enc(x4,K0)
num = list_to_int(CC1+CC2+CC3+CC4)
forward.add(num)
C_final0 = [0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1]
C_final1 = [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0]
C_final2 = [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1]
C_final3 = [0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1]
for i in tqdm(range(2**24)):
K1 = bin_to_list(i,24)
c_final0,c_final1,c_final2,c_final3 = [0]*16,[0]*16,[0]*16,[0]*16
for i0 in range(16):
c_final0[i0] = K1[8+i0]^C_final0[i0]
c_final1[i0] = K1[8+i0]^C_final1[i0]
c_final2[i0] = K1[8+i0]^C_final2[i0]
c_final3[i0] = K1[8+i0]^C_final3[i0]
C1,C2,C3,C4 = re_round_func(c_final0,2,K1),re_round_func(c_final1,2,K1),re_round_func(c_final2,2,K1),re_round_func(c_final3,2,K1)
C1,C2,C3,C4 = re_round_func(C1,1,K1),re_round_func(C2,1,K1),re_round_func(C3,1,K1),re_round_func(C4,1,K1)
num1 = list_to_int(C1+C2+C3+C4)
if num1 in forward:
print(K1)
break
得到后24bit的key，前八bit正向加密爆破。
from hashlib import sha256
from Crypto.Util.number import long_to_bytes
from tqdm import tqdm
def bin_to_list(r, bit_len):
list = [r >> d & 1 for d in range(bit_len)][::-1]
return list
def list_to_int(list):
return int("".join(str(i) for i in list), 2)
Pbox=[1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]
Sbox=[14, 13, 11, 0, 2, 1, 4, 15, 7, 10, 8, 5, 9, 12, 3, 6]
def round_func(X,r,K):
kstart=4*r - 4
XX = [0] * 16
for i in range(16):
XX[i] = X[i] ^ K[kstart+i]
for i in range(4):
value = list_to_int(XX[4*i:4*i+4])
s_value = Sbox[value]
s_list = bin_to_list(s_value, 4)
XX[4*i],XX[4*i+1],XX[4*i+2],XX[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]
Y=[0] * 16
for i in range(16):
Y[Pbox[i]-1]=XX[i]
return Y
def enc(X,K):
Y = round_func(X,1,K)
Y = round_func(Y,2,K)
Y = round_func(Y,3,K)
Y = round_func(Y,4,K)
kstart=4*5 - 4
for i in range(16):
Y[i] ^= K[kstart+i]
return Y
x1,x2,x3,x4 = [0]*16,[0]*16,[0]*16,[0]*16
x1[0],x2[4],x3[8],x4[12] = 1,1,1,1
k = [1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0]
for i in range(2**8):
key = bin_to_list(i,8) + k
C1,C2,C3,C4 = enc(x1,key),enc(x2,key),enc(x3,key),enc(x4,key)
if C1 == [0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1] and C2 == [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0]:
print(key)
hash_value = sha256(long_to_bytes(list_to_int(key))).hexdigest()
print(hash_value)
badrlwe
f = x^N - 1上存在问题，f可以分解为多个多项式相乘，可以找到 D^3CTF 2023中的d3bdd问题，f可以分为多个因子，于是降低degree使用LLL算法求出s关于不同f因子的余数，再使用crt求解，由于s最大度数不超过64，于是只需要求解f中度数小于64的因子即可。
from time import time
from Crypto.Util.number import *
from sage.all import *
from subprocess import check_output
from re import findall
q = 1219077173
F.<x> = Zmod(q)[]
N = 1024
x = F.gen()
f = x^N - 1
a = 216047404*x^1023 + 1008199117*x^1022 + 39562072*x^1021 + 189992355*x^1020 + 1087671639*x^1019 + 541371337*x^1018 + 1146044200*x^1017 + 212969175*x^1016 + 1114159572*x^1015 + 1112032860*x^1014 + 1204883609*x^1013 + 1181544913*x^1012 + 851496082*x^1011 + 222877006*x^1010 + 163176236*x^1009 + 268697504*x^1008 + 613151090*x^1007 + 1185245256*x^1006 + 215725010*x^1005 + 789898500*x^1004 + 1156619111*x^1003 + 610859911*x^1002 + 959814483*x^1001 + 684353251*x^1000 + 290850651*x^999 + 675880502*x^998 + 836239751*x^997 + 487296407*x^996 + 778816128*x^995 + 1013639221*x^994 + 189137575*x^993 + 172217836*x^992 + 572872008*x^991 + 865759581*x^990 + 399805736*x^989 + 394587004*x^988 + 633085719*x^987 + 15142893*x^986 + 461176831*x^985 + 1078060208*x^984 + 787396508*x^983 + 877420202*x^982 + 1121486845*x^981 + 146921816*x^980 + 670134387*x^979 + 574407635*x^978 + 1148395437*x^977 + 748514947*x^976 + 970442995*x^975 + 280085063*x^974 + 420670822*x^973 + 20159574*x^972 + 219680665*x^971 + 401202858*x^970 + 328444623*x^969 + 623312316*x^968 + 917712264*x^967 + 588061576*x^966 + 625482841*x^965 + 220929234*x^964 + 778461001*x^963 + 498203565*x^962 + 1055981771*x^961 + 70562147*x^960 + 931081750*x^959 + 93569863*x^958 + 314876311*x^957 + 932364613*x^956 + 1132016772*x^955 + 371703330*x^954 + 189301560*x^953 + 739232608*x^952 + 916695967*x^951 + 399818344*x^950 + 558604923*x^949 + 1092603913*x^948 + 987195616*x^947 + 665679589*x^946 + 1142632478*x^945 + 198797278*x^944 + 110832477*x^943 + 775688737*x^942 + 275416086*x^941 + 435656120*x^940 + 754150483*x^939 + 1024583186*x^938 + 972075461*x^937 + 1071060217*x^936 + 710789980*x^935 + 691361770*x^934 + 1097024307*x^933 + 862356288*x^932 + 354500195*x^931 + 158151296*x^930 + 733475281*x^929 + 215008492*x^928 + 151139272*x^927 + 1000425669*x^926 + 590964357*x^925 + 373950911*x^924 + 43038800*x^923 + 338044906*x^922 + 293954870*x^921 + 393479*x^920 + 555095359*x^919 + 418829106*x^918 + 95391760*x^917 + 897658305*x^916 + 1040609125*x^915 + 239948276*x^914 + 1190720461*x^913 + 160498737*x^912 + 394967890*x^911 + 104302686*x^910 + 48021969*x^909 + 761000569*x^908 + 356140410*x^907 + 225246587*x^906 + 79172445*x^905 + 975365689*x^904 + 1077396491*x^903 + 728717352*x^902 + 964273647*x^901 + 258781036*x^900 + 746930481*x^899 + 793742220*x^898 + 542128050*x^897 + 562413014*x^896 + 701216258*x^895 + 928704966*x^894 + 98656502*x^893 + 1016152774*x^892 + 140544845*x^891 + 226416702*x^890 + 309310359*x^889 + 519065123*x^888 + 346740110*x^887 + 116615122*x^886 + 990804519*x^885 + 208648062*x^884 + 605381435*x^883 + 821163414*x^882 + 864698754*x^881 + 424773230*x^880 + 1184139330*x^879 + 437390254*x^878 + 41435781*x^877 + 824197241*x^876 + 1181823353*x^875 + 354135255*x^874 + 921600154*x^873 + 972782404*x^872 + 304175744*x^871 + 976950586*x^870 + 561195955*x^869 + 840601911*x^868 + 848362310*x^867 + 698380233*x^866 + 703722831*x^865 + 527081934*x^864 + 996708932*x^863 + 926257884*x^862 + 113808466*x^861 + 111022399*x^860 + 336240881*x^859 + 281602555*x^858 + 456022351*x^857 + 303940681*x^856 + 1152960332*x^855 + 762827305*x^854 + 1097893502*x^853 + 1159492861*x^852 + 791288185*x^851 + 552596428*x^850 + 1160303133*x^849 + 855459983*x^848 + 870046128*x^847 + 412042730*x^846 + 527317697*x^845 + 118258027*x^844 + 1156090191*x^843 + 1184418516*x^842 + 736914609*x^841 + 1042440949*x^840 + 1118336201*x^839 + 692314475*x^838 + 888141647*x^837 + 611975215*x^836 + 112482309*x^835 + 774541929*x^834 + 877613260*x^833 + 218484596*x^832 + 744043072*x^831 + 1149426359*x^830 + 1086732941*x^829 + 218727414*x^828 + 111004493*x^827 + 48035668*x^826 + 1129753198*x^825 + 410088959*x^824 + 1186919074*x^823 + 291266088*x^822 + 622780685*x^821 + 908030149*x^820 + 152548456*x^819 + 970996704*x^818 + 643233117*x^817 + 97648457*x^816 + 167039372*x^815 + 451159004*x^814 + 21522258*x^813 + 446568222*x^812 + 97236135*x^811 + 601480363*x^810 + 896523050*x^809 + 635312918*x^808 + 771155729*x^807 + 727217487*x^806 + 1103325662*x^805 + 1145702253*x^804 + 111451279*x^803 + 709647761*x^802 + 155865734*x^801 + 788861657*x^800 + 25328658*x^799 + 387592047*x^798 + 631380316*x^797 + 195654331*x^796 + 379901017*x^795 + 110746571*x^794 + 821639667*x^793 + 1196705497*x^792 + 926725497*x^791 + 752090468*x^790 + 565928514*x^789 + 107924077*x^788 + 1035444397*x^787 + 389590222*x^786 + 746022468*x^785 + 1152494936*x^784 + 1047183126*x^783 + 935173423*x^782 + 237022259*x^781 + 68211471*x^780 + 682392084*x^779 + 900610142*x^778 + 659697118*x^777 + 381789469*x^776 + 895479393*x^775 + 342674862*x^774 + 1034152415*x^773 + 736863278*x^772 + 233824501*x^771 + 511543257*x^770 + 43539547*x^769 + 871109943*x^768 + 234226499*x^767 + 958639125*x^766 + 913885377*x^765 + 757234386*x^764 + 330354514*x^763 + 693659124*x^762 + 46757147*x^761 + 24910108*x^760 + 263754046*x^759 + 1007999117*x^758 + 569158879*x^757 + 781185896*x^756 + 328234792*x^755 + 1166796778*x^754 + 1023882729*x^753 + 1126014838*x^752 + 412948341*x^751 + 745762031*x^750 + 184601330*x^749 + 1195686854*x^748 + 226180761*x^747 + 813440273*x^746 + 198496604*x^745 + 646284299*x^744 + 775658802*x^743 + 1051631440*x^742 + 382010443*x^741 + 884529292*x^740 + 1171509241*x^739 + 148470016*x^738 + 545551560*x^737 + 895321797*x^736 + 990533556*x^735 + 1006826878*x^734 + 444425261*x^733 + 538658289*x^732 + 1201448839*x^731 + 813543244*x^730 + 866138640*x^729 + 992484781*x^728 + 797592952*x^727 + 5350520*x^726 + 1088776239*x^725 + 1011384293*x^724 + 202279961*x^723 + 580990742*x^722 + 608736084*x^721 + 592191483*x^720 + 603821965*x^719 + 686032966*x^718 + 309449994*x^717 + 997796743*x^716 + 323694959*x^715 + 404631321*x^714 + 684041814*x^713 + 954922509*x^712 + 17334061*x^711 + 1038027065*x^710 + 189030167*x^709 + 238786122*x^708 + 854157242*x^707 + 857322405*x^706 + 847505723*x^705 + 531600098*x^704 + 413144959*x^703 + 150862275*x^702 + 176120020*x^701 + 147651128*x^700 + 20961937*x^699 + 924892688*x^698 + 207889399*x^697 + 506289209*x^696 + 201657090*x^695 + 866897606*x^694 + 282950189*x^693 + 484625027*x^692 + 720969770*x^691 + 557487808*x^690 + 664292309*x^689 + 667236796*x^688 + 505039446*x^687 + 636507041*x^686 + 717904854*x^685 + 742491214*x^684 + 235380401*x^683 + 885103138*x^682 + 227708439*x^681 + 195450351*x^680 + 914408549*x^679 + 890140153*x^678 + 959662247*x^677 + 655663410*x^676 + 682768547*x^675 + 1063757282*x^674 + 776284911*x^673 + 1114588219*x^672 + 689022198*x^671 + 1160585767*x^670 + 784564493*x^669 + 599804982*x^668 + 954265199*x^667 + 1160092910*x^666 + 1178991310*x^665 + 610146522*x^664 + 589028938*x^663 + 972903553*x^662 + 933544074*x^661 + 910101746*x^660 + 1199479046*x^659 + 129564572*x^658 + 16630574*x^657 + 604268174*x^656 + 905616984*x^655 + 229755095*x^654 + 543777663*x^653 + 880642044*x^652 + 750742780*x^651 + 801027824*x^650 + 59869899*x^649 + 178293151*x^648 + 413473523*x^647 + 790966353*x^646 + 36947608*x^645 + 215402931*x^644 + 198271237*x^643 + 394503398*x^642 + 933396244*x^641 + 764498758*x^640 + 960831635*x^639 + 710558646*x^638 + 160491214*x^637 + 161213508*x^636 + 932611994*x^635 + 226519192*x^634 + 554464756*x^633 + 82595536*x^632 + 1144714763*x^631 + 361090580*x^630 + 747809061*x^629 + 114293244*x^628 + 253349999*x^627 + 1051279816*x^626 + 1079507344*x^625 + 864605458*x^624 + 1100098300*x^623 + 323233106*x^622 + 1070769430*x^621 + 1048471132*x^620 + 23281664*x^619 + 1099148878*x^618 + 812556000*x^617 + 452606567*x^616 + 892217880*x^615 + 741556204*x^614 + 37168552*x^613 + 286980867*x^612 + 1125383508*x^611 + 782814488*x^610 + 1214851511*x^609 + 270577673*x^608 + 364433480*x^607 + 825553809*x^606 + 589475297*x^605 + 293114041*x^604 + 1115978872*x^603 + 21831218*x^602 + 856821602*x^601 + 213782489*x^600 + 287159884*x^599 + 1015101950*x^598 + 494211644*x^597 + 38143731*x^596 + 882805771*x^595 + 721674528*x^594 + 120092153*x^593 + 636819567*x^592 + 365557574*x^591 + 619653423*x^590 + 1207892829*x^589 + 971282528*x^588 + 379459809*x^587 + 507124241*x^586 + 1050378769*x^585 + 113715629*x^584 + 841835564*x^583 + 1055649818*x^582 + 904319486*x^581 + 83232231*x^580 + 282044435*x^579 + 11563226*x^578 + 283283452*x^577 + 515932154*x^576 + 415242679*x^575 + 686396058*x^574 + 414011723*x^573 + 22692318*x^572 + 593039855*x^571 + 42054428*x^570 + 242713788*x^569 + 756543053*x^568 + 297264974*x^567 + 656668981*x^566 + 103185189*x^565 + 279211827*x^564 + 66472175*x^563 + 221289056*x^562 + 418547255*x^561 + 587378319*x^560 + 781217899*x^559 + 828907515*x^558 + 1026785730*x^557 + 936576598*x^556 + 914519864*x^555 + 458326840*x^554 + 846364356*x^553 + 1048948157*x^552 + 276890468*x^551 + 211463242*x^550 + 611009955*x^549 + 41350370*x^548 + 1120260432*x^547 + 1217213406*x^546 + 1096884636*x^545 + 107298827*x^544 + 556646889*x^543 + 514714957*x^542 + 592531623*x^541 + 1185635127*x^540 + 866796164*x^539 + 1199009440*x^538 + 760543377*x^537 + 135043128*x^536 + 1184521976*x^535 + 53368352*x^534 + 614063947*x^533 + 117184488*x^532 + 1090625549*x^531 + 928160285*x^530 + 1065640157*x^529 + 307397590*x^528 + 383318068*x^527 + 890835908*x^526 + 416986540*x^525 + 222852700*x^524 + 965323537*x^523 + 151764017*x^522 + 193722745*x^521 + 439803983*x^520 + 942882901*x^519 + 56286764*x^518 + 824204572*x^517 + 478793274*x^516 + 183238303*x^515 + 922253103*x^514 + 5444136*x^513 + 402856270*x^512 + 508652113*x^511 + 898341402*x^510 + 56743140*x^509 + 179078829*x^508 + 360574641*x^507 + 691533190*x^506 + 982373838*x^505 + 719429684*x^504 + 962339948*x^503 + 1097706834*x^502 + 682588935*x^501 + 1193566532*x^500 + 1140505780*x^499 + 1167874911*x^498 + 669408623*x^497 + 15348570*x^496 + 896129486*x^495 + 100671957*x^494 + 1015786650*x^493 + 605094306*x^492 + 704959137*x^491 + 503877361*x^490 + 546763047*x^489 + 281625173*x^488 + 874599768*x^487 + 187483443*x^486 + 791213383*x^485 + 670376251*x^484 + 484751013*x^483 + 519454749*x^482 + 898655062*x^481 + 1088862155*x^480 + 843442957*x^479 + 429341712*x^478 + 869408179*x^477 + 921648096*x^476 + 526019939*x^475 + 856290375*x^474 + 531710459*x^473 + 1135323038*x^472 + 222776023*x^471 + 223826994*x^470 + 782612384*x^469 + 208579370*x^468 + 809908930*x^467 + 802818642*x^466 + 1182584545*x^465 + 245518705*x^464 + 114792460*x^463 + 646248449*x^462 + 63969962*x^461 + 761908644*x^460 + 523665668*x^459 + 1131060959*x^458 + 507746193*x^457 + 215968166*x^456 + 186113215*x^455 + 1117740378*x^454 + 649175082*x^453 + 396834257*x^452 + 274002774*x^451 + 626055138*x^450 + 924423066*x^449 + 81357715*x^448 + 1042994674*x^447 + 380053163*x^446 + 687766657*x^445 + 414805559*x^444 + 1118153385*x^443 + 1196507975*x^442 + 223759358*x^441 + 808836890*x^440 + 558230978*x^439 + 470920831*x^438 + 313868031*x^437 + 696317665*x^436 + 38725962*x^435 + 722983488*x^434 + 982704221*x^433 + 931470025*x^432 + 658261117*x^431 + 1043739465*x^430 + 422603501*x^429 + 879856656*x^428 + 977082068*x^427 + 593021461*x^426 + 955543544*x^425 + 194004912*x^424 + 1057355064*x^423 + 1153279801*x^422 + 1104874965*x^421 + 1157109085*x^420 + 54358054*x^419 + 802241073*x^418 + 489376522*x^417 + 250441773*x^416 + 740903923*x^415 + 81493461*x^414 + 966046559*x^413 + 295086523*x^412 + 1192114766*x^411 + 1186654005*x^410 + 768853461*x^409 + 302013033*x^408 + 1127093874*x^407 + 401944628*x^406 + 463364841*x^405 + 277324527*x^404 + 357826211*x^403 + 302642912*x^402 + 785232813*x^401 + 1155455395*x^400 + 240939622*x^399 + 1090741169*x^398 + 941697407*x^397 + 1108935255*x^396 + 63027943*x^395 + 415750779*x^394 + 36046273*x^393 + 172429619*x^392 + 563533800*x^391 + 961503349*x^390 + 356454474*x^389 + 586712431*x^388 + 572728001*x^387 + 670855384*x^386 + 268877633*x^385 + 51139525*x^384 + 806328542*x^383 + 790061093*x^382 + 140256246*x^381 + 430118720*x^380 + 924612224*x^379 + 923573107*x^378 + 1124645882*x^377 + 1044890409*x^376 + 509180566*x^375 + 371227114*x^374 + 161843486*x^373 + 296514161*x^372 + 454272518*x^371 + 755779732*x^370 + 295567281*x^369 + 1063635155*x^368 + 46603670*x^367 + 112353112*x^366 + 571920305*x^365 + 484055586*x^364 + 148075787*x^363 + 700140701*x^362 + 922814151*x^361 + 198283677*x^360 + 806078101*x^359 + 1218701262*x^358 + 679274064*x^357 + 408382456*x^356 + 284971608*x^355 + 1072737570*x^354 + 999420946*x^353 + 704897365*x^352 + 1147239838*x^351 + 1148707218*x^350 + 119677974*x^349 + 139766009*x^348 + 289899118*x^347 + 3099746*x^346 + 478334394*x^345 + 671867092*x^344 + 1123276962*x^343 + 1053910974*x^342 + 776016929*x^341 + 408840884*x^340 + 702734268*x^339 + 101137143*x^338 + 157330682*x^337 + 608473559*x^336 + 355406102*x^335 + 1189624142*x^334 + 87874850*x^333 + 1097033743*x^332 + 984835279*x^331 + 133446104*x^330 + 990221835*x^329 + 34152703*x^328 + 902602955*x^327 + 564227604*x^326 + 378045277*x^325 + 330935315*x^324 + 300442927*x^323 + 504016276*x^322 + 592727454*x^321 + 1075766200*x^320 + 718996149*x^319 + 823573424*x^318 + 834215705*x^317 + 430497892*x^316 + 879722938*x^315 + 968236501*x^314 + 262764692*x^313 + 37503817*x^312 + 607855810*x^311 + 1173289902*x^310 + 906609932*x^309 + 11948749*x^308 + 948969610*x^307 + 1130417155*x^306 + 892108695*x^305 + 1040897188*x^304 + 174698274*x^303 + 85414336*x^302 + 758730292*x^301 + 615781943*x^300 + 1215130735*x^299 + 1168693743*x^298 + 1070287857*x^297 + 501559848*x^296 + 485147924*x^295 + 1218893131*x^294 + 923876087*x^293 + 565056561*x^292 + 282754375*x^291 + 794028720*x^290 + 288419549*x^289 + 688387454*x^288 + 40339086*x^287 + 659115548*x^286 + 614342861*x^285 + 391568544*x^284 + 464738754*x^283 + 28669498*x^282 + 1115640335*x^281 + 870635325*x^280 + 126237247*x^279 + 1111165998*x^278 + 205027579*x^277 + 911218811*x^276 + 208748481*x^275 + 725176545*x^274 + 765151044*x^273 + 939495648*x^272 + 550038893*x^271 + 905707993*x^270 + 267107699*x^269 + 477779883*x^268 + 251985659*x^267 + 754082836*x^266 + 159569451*x^265 + 781616103*x^264 + 1098961576*x^263 + 1139687026*x^262 + 473401848*x^261 + 623689501*x^260 + 1012676202*x^259 + 76777202*x^258 + 170602576*x^257 + 266093330*x^256 + 732274753*x^255 + 193219366*x^254 + 610602682*x^253 + 749761392*x^252 + 536911921*x^251 + 1052883954*x^250 + 1139729422*x^249 + 617278363*x^248 + 603450863*x^247 + 877968049*x^246 + 1078543204*x^245 + 441578327*x^244 + 821469144*x^243 + 1083268726*x^242 + 592074734*x^241 + 431251183*x^240 + 1151073027*x^239 + 596034003*x^238 + 507176703*x^237 + 638155464*x^236 + 820097610*x^235 + 69713965*x^234 + 111089281*x^233 + 403306683*x^232 + 417322569*x^231 + 510992488*x^230 + 406068742*x^229 + 487323397*x^228 + 1105866147*x^227 + 126043214*x^226 + 565379393*x^225 + 774566507*x^224 + 94477834*x^223 + 301787901*x^222 + 891557978*x^221 + 246179873*x^220 + 76065360*x^219 + 632831219*x^218 + 967852970*x^217 + 982932236*x^216 + 457056482*x^215 + 611696056*x^214 + 187879254*x^213 + 919970751*x^212 + 726626422*x^211 + 744906999*x^210 + 514152204*x^209 + 400846913*x^208 + 1057213516*x^207 + 458393393*x^206 + 39867352*x^205 + 482474421*x^204 + 1017159775*x^203 + 1127386440*x^202 + 186890818*x^201 + 297371952*x^200 + 827010510*x^199 + 457757189*x^198 + 120047360*x^197 + 403406161*x^196 + 561776540*x^195 + 269984973*x^194 + 1105865523*x^193 + 356682370*x^192 + 521018201*x^191 + 714326305*x^190 + 230112489*x^189 + 468954949*x^188 + 428412182*x^187 + 418097923*x^186 + 648421330*x^185 + 119412602*x^184 + 1029175202*x^183 + 961854350*x^182 + 359274957*x^181 + 918516748*x^180 + 393392054*x^179 + 998769881*x^178 + 713880369*x^177 + 23918875*x^176 + 19140072*x^175 + 296443203*x^174 + 1036511543*x^173 + 208417465*x^172 + 856221174*x^171 + 724608949*x^170 + 1148614286*x^169 + 605394185*x^168 + 1037184954*x^167 + 1149508482*x^166 + 748219008*x^165 + 762595570*x^164 + 240812860*x^163 + 221590855*x^162 + 921277317*x^161 + 666749995*x^160 + 270085731*x^159 + 719780654*x^158 + 1023109552*x^157 + 948736441*x^156 + 942460534*x^155 + 1190076672*x^154 + 298412436*x^153 + 146236637*x^152 + 136974417*x^151 + 247369427*x^150 + 1164600849*x^149 + 80725190*x^148 + 563971590*x^147 + 838975230*x^146 + 605884308*x^145 + 695738052*x^144 + 457993644*x^143 + 608089160*x^142 + 279768415*x^141 + 167776427*x^140 + 99830319*x^139 + 724761513*x^138 + 838344856*x^137 + 349705095*x^136 + 700591961*x^135 + 495192008*x^134 + 166834844*x^133 + 829383641*x^132 + 689577635*x^131 + 1063098370*x^130 + 1217658142*x^129 + 210005674*x^128 + 709445493*x^127 + 890260692*x^126 + 11818873*x^125 + 356866298*x^124 + 657354178*x^123 + 1083325742*x^122 + 256937537*x^121 + 832141251*x^120 + 738779202*x^119 + 531375449*x^118 + 570407521*x^117 + 253499493*x^116 + 936295735*x^115 + 840539077*x^114 + 1108243632*x^113 + 518037787*x^112 + 512681158*x^111 + 659791034*x^110 + 615039004*x^109 + 6475754*x^108 + 112655504*x^107 + 135513268*x^106 + 814830817*x^105 + 312451349*x^104 + 459204360*x^103 + 536270797*x^102 + 487599107*x^101 + 995873996*x^100 + 947176358*x^99 + 161110841*x^98 + 1215850742*x^97 + 828031021*x^96 + 393857015*x^95 + 483165571*x^94 + 1169422374*x^93 + 185485308*x^92 + 1113820447*x^91 + 1217012548*x^90 + 591690262*x^89 + 230984245*x^88 + 1183186281*x^87 + 984746087*x^86 + 321334226*x^85 + 356396152*x^84 + 812358214*x^83 + 652862462*x^82 + 1159946831*x^81 + 1185692555*x^80 + 1101691161*x^79 + 1162783803*x^78 + 592033894*x^77 + 545367197*x^76 + 441688164*x^75 + 169491076*x^74 + 181297517*x^73 + 590332818*x^72 + 814337101*x^71 + 1148316386*x^70 + 700258144*x^69 + 719201877*x^68 + 1160695934*x^67 + 1186868159*x^66 + 508542038*x^65 + 1113702100*x^64 + 921032142*x^63 + 758636144*x^62 + 890540800*x^61 + 136808203*x^60 + 74886413*x^59 + 156077420*x^58 + 925473910*x^57 + 111404286*x^56 + 355116767*x^55 + 468038980*x^54 + 89708844*x^53 + 878616521*x^52 + 1154657871*x^51 + 677831135*x^50 + 903468800*x^49 + 890557208*x^48 + 1035114476*x^47 + 198189399*x^46 + 864375452*x^45 + 1164916963*x^44 + 929627324*x^43 + 418711325*x^42 + 97430691*x^41 + 1172413774*x^40 + 760600756*x^39 + 943281805*x^38 + 53033182*x^37 + 123566782*x^36 + 665472336*x^35 + 521103310*x^34 + 892876972*x^33 + 169828417*x^32 + 315862403*x^31 + 973295601*x^30 + 1036868940*x^29 + 469235131*x^28 + 1097609240*x^27 + 446027303*x^26 + 356219098*x^25 + 480790123*x^24 + 94742566*x^23 + 691728720*x^22 + 922852954*x^21 + 21648854*x^20 + 903452116*x^19 + 1043050543*x^18 + 867501915*x^17 + 402312961*x^16 + 772349320*x^15 + 806410607*x^14 + 573402289*x^13 + 103888540*x^12 + 147927873*x^11 + 1005161156*x^10 + 988774771*x^9 + 682875980*x^8 + 54946232*x^7 + 717143945*x^6 + 323577100*x^5 + 803064428*x^4 + 598462622*x^3 + 1110253556*x^2 + 764371182*x + 634648371
b = 735531500*x^1023 + 684755229*x^1022 + 978579144*x^1021 + 560225565*x^1020 + 758090578*x^1019 + 367477932*x^1018 + 326779415*x^1017 + 26800946*x^1016 + 199017905*x^1015 + 1156874439*x^1014 + 673969262*x^1013 + 617169647*x^1012 + 462256026*x^1011 + 303059784*x^1010 + 663728970*x^1009 + 376865711*x^1008 + 830705685*x^1007 + 573964358*x^1006 + 1210202059*x^1005 + 269197755*x^1004 + 586236496*x^1003 + 621987820*x^1002 + 485567868*x^1001 + 305700227*x^1000 + 1052698462*x^999 + 86861550*x^998 + 44767901*x^997 + 410897986*x^996 + 212344404*x^995 + 336381747*x^994 + 398182335*x^993 + 660275371*x^992 + 52728322*x^991 + 1193103469*x^990 + 684295535*x^989 + 1029981794*x^988 + 1051866415*x^987 + 418681909*x^986 + 976794520*x^985 + 1180496804*x^984 + 438513041*x^983 + 822843942*x^982 + 1119264881*x^981 + 790873853*x^980 + 1146506838*x^979 + 27016797*x^978 + 1149126201*x^977 + 967895459*x^976 + 1201841165*x^975 + 264216641*x^974 + 751855165*x^973 + 277480010*x^972 + 955969328*x^971 + 784721168*x^970 + 696371212*x^969 + 401164998*x^968 + 654719011*x^967 + 785183205*x^966 + 79070435*x^965 + 1140562925*x^964 + 1025154340*x^963 + 1044315421*x^962 + 392734282*x^961 + 234286141*x^960 + 962551866*x^959 + 133742245*x^958 + 998056106*x^957 + 781318236*x^956 + 23528574*x^955 + 1214036424*x^954 + 296666931*x^953 + 1211729921*x^952 + 561550286*x^951 + 634392845*x^950 + 422332555*x^949 + 765556851*x^948 + 1151849524*x^947 + 305981530*x^946 + 246290056*x^945 + 24304550*x^944 + 477073522*x^943 + 416104453*x^942 + 898162013*x^941 + 611609496*x^940 + 445765799*x^939 + 430180169*x^938 + 1151421310*x^937 + 439515367*x^936 + 795257572*x^935 + 578106992*x^934 + 929259980*x^933 + 550407102*x^932 + 1219047347*x^931 + 15972593*x^930 + 515513177*x^929 + 679675449*x^928 + 914537835*x^927 + 156230965*x^926 + 385558312*x^925 + 1036365654*x^924 + 1098274877*x^923 + 348628203*x^922 + 1093802915*x^921 + 1162728002*x^920 + 200502246*x^919 + 551049082*x^918 + 969116717*x^917 + 1127382445*x^916 + 968172543*x^915 + 346881523*x^914 + 41744706*x^913 + 335042561*x^912 + 593895276*x^911 + 15888292*x^910 + 324866127*x^909 + 937351605*x^908 + 347255852*x^907 + 1120419679*x^906 + 249832197*x^905 + 896923860*x^904 + 129801128*x^903 + 207849052*x^902 + 386825059*x^901 + 823406098*x^900 + 977635408*x^899 + 108813100*x^898 + 561865827*x^897 + 718000532*x^896 + 48090035*x^895 + 832337939*x^894 + 1084389292*x^893 + 793335438*x^892 + 1095245016*x^891 + 1080787282*x^890 + 122666287*x^889 + 937313249*x^888 + 62818846*x^887 + 1170462486*x^886 + 182439366*x^885 + 792906343*x^884 + 1205386767*x^883 + 310389549*x^882 + 603676058*x^881 + 671251954*x^880 + 640345010*x^879 + 1087374504*x^878 + 119769446*x^877 + 135989573*x^876 + 880703983*x^875 + 613578242*x^874 + 1207874966*x^873 + 972002390*x^872 + 644470053*x^871 + 335762119*x^870 + 1079917808*x^869 + 1023711373*x^868 + 861485470*x^867 + 230979333*x^866 + 683284149*x^865 + 645804102*x^864 + 577971621*x^863 + 33779989*x^862 + 915467237*x^861 + 834966216*x^860 + 445758874*x^859 + 685228217*x^858 + 979609284*x^857 + 842509205*x^856 + 221373358*x^855 + 150166201*x^854 + 927937340*x^853 + 995054125*x^852 + 704623324*x^851 + 1112892592*x^850 + 782816865*x^849 + 878518510*x^848 + 391872241*x^847 + 30062686*x^846 + 108900016*x^845 + 1034780269*x^844 + 1190084541*x^843 + 441686497*x^842 + 117953957*x^841 + 840802549*x^840 + 903238790*x^839 + 551715093*x^838 + 539420097*x^837 + 1007110444*x^836 + 673864283*x^835 + 756402005*x^834 + 197892310*x^833 + 981720851*x^832 + 798897509*x^831 + 1127242378*x^830 + 666754217*x^829 + 685248618*x^828 + 327773092*x^827 + 390697118*x^826 + 912223373*x^825 + 482947333*x^824 + 1110169857*x^823 + 780612147*x^822 + 194698743*x^821 + 716386043*x^820 + 424946693*x^819 + 22701975*x^818 + 293011366*x^817 + 947695756*x^816 + 1188483932*x^815 + 1002073886*x^814 + 1078210750*x^813 + 1127684166*x^812 + 719332394*x^811 + 1072532713*x^810 + 550629553*x^809 + 188195613*x^808 + 614412704*x^807 + 649960359*x^806 + 1010011298*x^805 + 824975518*x^804 + 311757403*x^803 + 93674481*x^802 + 380323800*x^801 + 1086623904*x^800 + 240170088*x^799 + 956396081*x^798 + 939969890*x^797 + 131843464*x^796 + 1045744996*x^795 + 424359277*x^794 + 550616456*x^793 + 1061637035*x^792 + 444548551*x^791 + 677546521*x^790 + 149605032*x^789 + 829567560*x^788 + 516053142*x^787 + 1191529914*x^786 + 294270928*x^785 + 142024389*x^784 + 584911191*x^783 + 307856659*x^782 + 81514660*x^781 + 543784156*x^780 + 108008163*x^779 + 13154295*x^778 + 155266054*x^777 + 663702892*x^776 + 782494602*x^775 + 747547833*x^774 + 242456376*x^773 + 669844220*x^772 + 552894098*x^771 + 1036366706*x^770 + 1074841665*x^769 + 720745418*x^768 + 1137936670*x^767 + 840875363*x^766 + 476498840*x^765 + 1088669461*x^764 + 1249649*x^763 + 882277578*x^762 + 37842126*x^761 + 398977801*x^760 + 328296234*x^759 + 536342859*x^758 + 608139240*x^757 + 897424944*x^756 + 76562916*x^755 + 428081420*x^754 + 627420927*x^753 + 265131678*x^752 + 1034443577*x^751 + 177902661*x^750 + 490977141*x^749 + 1084536775*x^748 + 1189221123*x^747 + 854191429*x^746 + 952038058*x^745 + 891288300*x^744 + 929356576*x^743 + 223874272*x^742 + 220297702*x^741 + 1099283305*x^740 + 1008574448*x^739 + 619949004*x^738 + 747199791*x^737 + 760703880*x^736 + 7682727*x^735 + 88566484*x^734 + 733742620*x^733 + 381443925*x^732 + 799269923*x^731 + 233342676*x^730 + 1205696983*x^729 + 765306727*x^728 + 29342855*x^727 + 287728251*x^726 + 214358216*x^725 + 355991367*x^724 + 344973841*x^723 + 436344093*x^722 + 547944829*x^721 + 1041405031*x^720 + 368771692*x^719 + 37426577*x^718 + 502936636*x^717 + 732825913*x^716 + 518778589*x^715 + 561797784*x^714 + 773068766*x^713 + 75615306*x^712 + 668933267*x^711 + 628975723*x^710 + 1140697439*x^709 + 108807342*x^708 + 283945737*x^707 + 701674528*x^706 + 1120373548*x^705 + 421627231*x^704 + 260846853*x^703 + 292537012*x^702 + 583513440*x^701 + 609720259*x^700 + 831373721*x^699 + 1126099385*x^698 + 431095431*x^697 + 296863241*x^696 + 371013827*x^695 + 549980853*x^694 + 550174635*x^693 + 620963563*x^692 + 952040422*x^691 + 1150044500*x^690 + 893175261*x^689 + 1139857784*x^688 + 972717568*x^687 + 735672517*x^686 + 1177501026*x^685 + 765934764*x^684 + 710762091*x^683 + 871268519*x^682 + 969318271*x^681 + 286261161*x^680 + 65128931*x^679 + 1100922672*x^678 + 47619662*x^677 + 981578224*x^676 + 67232154*x^675 + 1928142*x^674 + 817643007*x^673 + 675713298*x^672 + 185236805*x^671 + 331446457*x^670 + 129023118*x^669 + 431426370*x^668 + 1154277684*x^667 + 723182950*x^666 + 1144823093*x^665 + 822001162*x^664 + 356099532*x^663 + 705989193*x^662 + 878712048*x^661 + 1095044481*x^660 + 332193401*x^659 + 613329359*x^658 + 673744151*x^657 + 808080280*x^656 + 225562949*x^655 + 185686220*x^654 + 742469973*x^653 + 986152315*x^652 + 13611550*x^651 + 535747170*x^650 + 233786507*x^649 + 27955348*x^648 + 1004446959*x^647 + 1071164149*x^646 + 265258708*x^645 + 63221383*x^644 + 682228580*x^643 + 867131152*x^642 + 997600620*x^641 + 993922001*x^640 + 693252545*x^639 + 865655581*x^638 + 518295141*x^637 + 902072633*x^636 + 704953646*x^635 + 587251157*x^634 + 99168972*x^633 + 1105480730*x^632 + 1040404159*x^631 + 436113220*x^630 + 152714904*x^629 + 697469981*x^628 + 1185372838*x^627 + 216027999*x^626 + 616083931*x^625 + 399419685*x^624 + 23193568*x^623 + 1174129641*x^622 + 75724376*x^621 + 570399858*x^620 + 754947446*x^619 + 1037864447*x^618 + 794730343*x^617 + 60369472*x^616 + 750769016*x^615 + 61444481*x^614 + 333194445*x^613 + 1109236037*x^612 + 513379869*x^611 + 706807998*x^610 + 999669914*x^609 + 1198194959*x^608 + 336044172*x^607 + 402719207*x^606 + 1050007981*x^605 + 429464593*x^604 + 679293134*x^603 + 734513317*x^602 + 838385265*x^601 + 990800608*x^600 + 1162093896*x^599 + 173467508*x^598 + 123947890*x^597 + 325712596*x^596 + 1049522320*x^595 + 1072653958*x^594 + 565759817*x^593 + 549918485*x^592 + 574268523*x^591 + 1052593520*x^590 + 474323970*x^589 + 262787725*x^588 + 1091470590*x^587 + 782664905*x^586 + 1201833996*x^585 + 808712564*x^584 + 619522329*x^583 + 233329446*x^582 + 730502283*x^581 + 1017501853*x^580 + 306080194*x^579 + 283641594*x^578 + 195324593*x^577 + 1116741123*x^576 + 289439631*x^575 + 206064600*x^574 + 280021778*x^573 + 425409216*x^572 + 1107952582*x^571 + 131800177*x^570 + 106903346*x^569 + 72306234*x^568 + 934072451*x^567 + 242740893*x^566 + 106611451*x^565 + 429378634*x^564 + 127624569*x^563 + 587315789*x^562 + 932709753*x^561 + 523886142*x^560 + 110330665*x^559 + 963244036*x^558 + 227339325*x^557 + 185882207*x^556 + 987833442*x^555 + 981380006*x^554 + 1140813804*x^553 + 538704418*x^552 + 842520362*x^551 + 597627400*x^550 + 165232274*x^549 + 900076209*x^548 + 311342603*x^547 + 477271753*x^546 + 1072907066*x^545 + 1066126181*x^544 + 791702251*x^543 + 623246063*x^542 + 1082681410*x^541 + 759396967*x^540 + 878108937*x^539 + 724607060*x^538 + 79223685*x^537 + 307312027*x^536 + 234246571*x^535 + 330319932*x^534 + 274254378*x^533 + 1082820468*x^532 + 68920838*x^531 + 1195376541*x^530 + 170971307*x^529 + 399525324*x^528 + 238798853*x^527 + 664426862*x^526 + 269949285*x^525 + 698202786*x^524 + 88964561*x^523 + 635539315*x^522 + 1016514687*x^521 + 122364467*x^520 + 1095096646*x^519 + 513834099*x^518 + 672478524*x^517 + 47526709*x^516 + 48782616*x^515 + 166225959*x^514 + 810099682*x^513 + 168540411*x^512 + 30055377*x^511 + 817325819*x^510 + 202717189*x^509 + 739906349*x^508 + 186072589*x^507 + 451966755*x^506 + 684027658*x^505 + 251331059*x^504 + 591972494*x^503 + 289197098*x^502 + 829928406*x^501 + 160528626*x^500 + 90951219*x^499 + 496118642*x^498 + 117818178*x^497 + 215417436*x^496 + 937904122*x^495 + 962080493*x^494 + 423647737*x^493 + 1094089608*x^492 + 97559711*x^491 + 412409151*x^490 + 1039695658*x^489 + 461079746*x^488 + 564664118*x^487 + 2231630*x^486 + 667569567*x^485 + 471400483*x^484 + 691739455*x^483 + 146641223*x^482 + 445509678*x^481 + 788647561*x^480 + 100316571*x^479 + 927803124*x^478 + 225739054*x^477 + 339283562*x^476 + 741552554*x^475 + 674303545*x^474 + 610706793*x^473 + 1045437706*x^472 + 758427998*x^471 + 518677374*x^470 + 1020530386*x^469 + 81672436*x^468 + 684553666*x^467 + 36416557*x^466 + 1083076029*x^465 + 63903696*x^464 + 655765095*x^463 + 464055997*x^462 + 874368360*x^461 + 909538282*x^460 + 1084815716*x^459 + 971305398*x^458 + 504958756*x^457 + 941782746*x^456 + 410981017*x^455 + 44463213*x^454 + 57796260*x^453 + 633624768*x^452 + 902476625*x^451 + 1190884714*x^450 + 30960289*x^449 + 698111360*x^448 + 507015564*x^447 + 595305556*x^446 + 1170147546*x^445 + 595449153*x^444 + 1132050715*x^443 + 566093951*x^442 + 1125890381*x^441 + 864044563*x^440 + 608408253*x^439 + 128031905*x^438 + 951152598*x^437 + 41054884*x^436 + 1012755213*x^435 + 1091670374*x^434 + 481898210*x^433 + 1007980179*x^432 + 43301236*x^431 + 6478999*x^430 + 1175215424*x^429 + 597862715*x^428 + 441537430*x^427 + 339705054*x^426 + 289227345*x^425 + 795113772*x^424 + 404870950*x^423 + 997272819*x^422 + 634256255*x^421 + 453060086*x^420 + 821493547*x^419 + 842289852*x^418 + 223251279*x^417 + 929721613*x^416 + 63980045*x^415 + 298369623*x^414 + 1026287144*x^413 + 979092254*x^412 + 1182904024*x^411 + 298048453*x^410 + 653297794*x^409 + 365769179*x^408 + 45373617*x^407 + 7228243*x^406 + 1086374067*x^405 + 389455721*x^404 + 992518297*x^403 + 433929335*x^402 + 1149626197*x^401 + 90006250*x^400 + 1011632630*x^399 + 940906615*x^398 + 564772117*x^397 + 692974220*x^396 + 561321375*x^395 + 1095715303*x^394 + 1006114558*x^393 + 95516055*x^392 + 640816811*x^391 + 869737844*x^390 + 248741996*x^389 + 101754352*x^388 + 253268107*x^387 + 593472036*x^386 + 627778298*x^385 + 801877646*x^384 + 286581226*x^383 + 645931883*x^382 + 373119745*x^381 + 461109006*x^380 + 594214135*x^379 + 751634451*x^378 + 706229440*x^377 + 247985412*x^376 + 993987710*x^375 + 618989435*x^374 + 600506682*x^373 + 179955505*x^372 + 956234357*x^371 + 1049030902*x^370 + 727597507*x^369 + 1196607714*x^368 + 610634244*x^367 + 619865634*x^366 + 849131167*x^365 + 1094185730*x^364 + 685353152*x^363 + 299082549*x^362 + 1076769237*x^361 + 792938001*x^360 + 885082721*x^359 + 1198739364*x^358 + 273154602*x^357 + 597517874*x^356 + 351418158*x^355 + 621945565*x^354 + 949756104*x^353 + 1020290901*x^352 + 315372660*x^351 + 291246927*x^350 + 1016861207*x^349 + 171467993*x^348 + 1074074496*x^347 + 660775696*x^346 + 562891589*x^345 + 258618000*x^344 + 521058831*x^343 + 152819838*x^342 + 1141330990*x^341 + 383408903*x^340 + 677850803*x^339 + 165908062*x^338 + 66975904*x^337 + 510786934*x^336 + 32306220*x^335 + 708115806*x^334 + 474352780*x^333 + 963188335*x^332 + 151844162*x^331 + 907339624*x^330 + 456166118*x^329 + 111742252*x^328 + 318018829*x^327 + 624012970*x^326 + 255354390*x^325 + 1218329311*x^324 + 375000855*x^323 + 54956044*x^322 + 13543809*x^321 + 671163260*x^320 + 226676913*x^319 + 1193470867*x^318 + 477161216*x^317 + 519506783*x^316 + 748987057*x^315 + 768531367*x^314 + 327816599*x^313 + 59056092*x^312 + 520958252*x^311 + 243337260*x^310 + 608632530*x^309 + 65258636*x^308 + 1012579720*x^307 + 400176357*x^306 + 104583966*x^305 + 1114827176*x^304 + 70705682*x^303 + 5320656*x^302 + 1207465008*x^301 + 1211372826*x^300 + 886104873*x^299 + 747144635*x^298 + 227753814*x^297 + 427912588*x^296 + 425232985*x^295 + 135219277*x^294 + 541439233*x^293 + 82586191*x^292 + 1024575564*x^291 + 408418547*x^290 + 1076407665*x^289 + 184646604*x^288 + 894569780*x^287 + 730742386*x^286 + 473643018*x^285 + 561906151*x^284 + 582231889*x^283 + 928617667*x^282 + 460594931*x^281 + 946340582*x^280 + 881007408*x^279 + 655553538*x^278 + 107738502*x^277 + 958107338*x^276 + 874269820*x^275 + 689734430*x^274 + 1025286771*x^273 + 809509338*x^272 + 126580761*x^271 + 425724981*x^270 + 91398446*x^269 + 915486182*x^268 + 750598785*x^267 + 331692120*x^266 + 266239686*x^265 + 41813860*x^264 + 1003196915*x^263 + 1006275694*x^262 + 958171508*x^261 + 387655573*x^260 + 529686749*x^259 + 2533683*x^258 + 851532040*x^257 + 515865631*x^256 + 331149910*x^255 + 1058283457*x^254 + 478391568*x^253 + 1020601120*x^252 + 193954604*x^251 + 125558467*x^250 + 916367669*x^249 + 965664721*x^248 + 737411958*x^247 + 145954639*x^246 + 787702411*x^245 + 256023548*x^244 + 831752864*x^243 + 637799028*x^242 + 202325459*x^241 + 189858829*x^240 + 221236168*x^239 + 276967229*x^238 + 732958371*x^237 + 31622618*x^236 + 558911372*x^235 + 257580689*x^234 + 490167674*x^233 + 1164269554*x^232 + 765931664*x^231 + 89716985*x^230 + 639008878*x^229 + 716033538*x^228 + 186948569*x^227 + 870251868*x^226 + 383121640*x^225 + 604362204*x^224 + 405526662*x^223 + 127371887*x^222 + 543669202*x^221 + 823112915*x^220 + 523517382*x^219 + 791437322*x^218 + 1069279817*x^217 + 960628355*x^216 + 1012582276*x^215 + 1200088601*x^214 + 927011022*x^213 + 830570829*x^212 + 700668365*x^211 + 1205573850*x^210 + 276778781*x^209 + 786305215*x^208 + 928215922*x^207 + 154393796*x^206 + 169298902*x^205 + 177646296*x^204 + 173339370*x^203 + 287217637*x^202 + 1077403939*x^201 + 1004965535*x^200 + 677352462*x^199 + 545192340*x^198 + 464170452*x^197 + 381853900*x^196 + 205643848*x^195 + 973330672*x^194 + 1148733662*x^193 + 458436519*x^192 + 68604889*x^191 + 193530886*x^190 + 141661386*x^189 + 1117183144*x^188 + 153035244*x^187 + 830892599*x^186 + 795500906*x^185 + 67041425*x^184 + 617209634*x^183 + 180547177*x^182 + 1183445159*x^181 + 303603618*x^180 + 842724764*x^179 + 784982658*x^178 + 1199356684*x^177 + 321497016*x^176 + 513738925*x^175 + 465949450*x^174 + 981246204*x^173 + 814398377*x^172 + 950247970*x^171 + 720838080*x^170 + 399493165*x^169 + 735365971*x^168 + 109745845*x^167 + 897998838*x^166 + 547497972*x^165 + 174675208*x^164 + 716115074*x^163 + 237209800*x^162 + 186394653*x^161 + 876995839*x^160 + 1187252196*x^159 + 819282320*x^158 + 44596523*x^157 + 679033559*x^156 + 736746236*x^155 + 1184916922*x^154 + 451294643*x^153 + 443590366*x^152 + 304384335*x^151 + 1064695584*x^150 + 602535518*x^149 + 684486124*x^148 + 863476315*x^147 + 496170722*x^146 + 737062216*x^145 + 285799611*x^144 + 1085153158*x^143 + 247783563*x^142 + 1208043659*x^141 + 208776666*x^140 + 117730360*x^139 + 279620264*x^138 + 273045622*x^137 + 893971194*x^136 + 240743423*x^135 + 1143029271*x^134 + 326725356*x^133 + 294174585*x^132 + 672819095*x^131 + 138843366*x^130 + 1176670148*x^129 + 573825049*x^128 + 835249905*x^127 + 778468469*x^126 + 300257393*x^125 + 409352854*x^124 + 953527813*x^123 + 653640743*x^122 + 1210615840*x^121 + 596684403*x^120 + 46012813*x^119 + 510765516*x^118 + 1213476223*x^117 + 1132779740*x^116 + 769195645*x^115 + 963749389*x^114 + 843804183*x^113 + 109759209*x^112 + 493130294*x^111 + 1122857844*x^110 + 1130618881*x^109 + 648465049*x^108 + 364595574*x^107 + 410134064*x^106 + 597836905*x^105 + 831243271*x^104 + 226275998*x^103 + 686704033*x^102 + 662011231*x^101 + 112226051*x^100 + 623946037*x^99 + 469742204*x^98 + 369854172*x^97 + 731154062*x^96 + 352916654*x^95 + 45991298*x^94 + 614913911*x^93 + 632337602*x^92 + 327529986*x^91 + 111251878*x^90 + 657089210*x^89 + 499853920*x^88 + 966818975*x^87 + 454584975*x^86 + 116582431*x^85 + 619242494*x^84 + 455382561*x^83 + 246350547*x^82 + 495191129*x^81 + 900852972*x^80 + 264825752*x^79 + 426813960*x^78 + 478124215*x^77 + 1080567657*x^76 + 858353771*x^75 + 215115660*x^74 + 963682245*x^73 + 964445096*x^72 + 73603206*x^71 + 734630202*x^70 + 199652522*x^69 + 520021635*x^68 + 763256200*x^67 + 861482624*x^66 + 890485659*x^65 + 523362913*x^64 + 785087110*x^63 + 381314881*x^62 + 843850504*x^61 + 61951613*x^60 + 119100925*x^59 + 531827488*x^58 + 199818669*x^57 + 592207491*x^56 + 354682041*x^55 + 1015447358*x^54 + 328324806*x^53 + 24880841*x^52 + 516663598*x^51 + 716706066*x^50 + 1042483154*x^49 + 331433641*x^48 + 929901382*x^47 + 502140671*x^46 + 48123362*x^45 + 1112586174*x^44 + 14618102*x^43 + 764832169*x^42 + 446768463*x^41 + 920421919*x^40 + 491851586*x^39 + 24718814*x^38 + 83091454*x^37 + 155770396*x^36 + 12824441*x^35 + 954371888*x^34 + 318592841*x^33 + 788251579*x^32 + 246435934*x^31 + 387083299*x^30 + 395226231*x^29 + 646811732*x^28 + 1131418388*x^27 + 1135116504*x^26 + 986902782*x^25 + 323457413*x^24 + 521885110*x^23 + 234655676*x^22 + 965166497*x^21 + 755967054*x^20 + 574743395*x^19 + 1175664410*x^18 + 117322371*x^17 + 794664856*x^16 + 570463*x^15 + 1148572518*x^14 + 439320220*x^13 + 815953366*x^12 + 389050726*x^11 + 1167287391*x^10 + 397052468*x^9 + 275572458*x^8 + 548665509*x^7 + 1202175986*x^6 + 518662014*x^5 + 1084425257*x^4 + 7854568*x^3 + 274607457*x^2 + 162444786*x + 410560230
ps = [x - 1,x + 1,x^2 + 1,x^4 + 1,x^8 + 1,x^16 + 1,x^32 + 1,x^64 + 1]
def flatter(M):
# compile https://github.com/keeganryan/flatter and put it in $PATH
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
ret = check_output(["flatter"], input=z.encode())
return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
def solve(poly, a, b, slen=None):
# solve for a*s+e=b (mod poly)
# where s and e are small
# and len(s) = slen
global mat, mat2
n = poly.degree()
if slen is None:
slen = n
print(f"Try solving with deg(poly) = {n}")
t0 = time()
main_block = matrix([vector(a * x**i % poly) for i in range(n)])
approx = 512 // n # approximation for the average of target vector
mat = block_matrix(
ZZ,
[
[1, -main_block, 0],
[0, q, 0],
# kannan embedding
[
0,
matrix(vector(b % poly)),
matrix([[approx]]),
],
],
)
mat[:, slen:n] *= q # force zero
print(f"Lattice size = {mat.dimensions()}")
mat2 = flatter(mat)
print(f"{mat.nrows()}x{mat.ncols()} lattice reduced in {time()-t0}")
for ret in mat2:
if ret[-1] < 0:
ret = -ret
if ret[-1] == approx:
print(ret)
print()
return F(list(ret[:n]))
rs = [solve(p, a, b) for p in ps]
L = lcm(ps[:-1]) # deg(L) = 256
s_mod_L = crt(rs, ps) # this is s (mod L)
e_mod_L = (b - a * s_mod_L) % L
print('---------------')
print(s_mod_L)
print(e_mod_L)
q = 1219077173
P.<x> = PolynomialRing(Zmod(q))
A = 114*x^63 + 49*x^62 + 104*x^61 + 56*x^60 + 84*x^59 + 49*x^58 + 60*x^57 + 37*x^56 + 36*x^55 + 55*x^54 + 106*x^53 + 40*x^52 + 111*x^51 + 61*x^50 + 111*x^49 + 68*x^48 + 111*x^47 + 125*x^46 + 81*x^45 + 68*x^44 + 35*x^43 + 53*x^42 + 94*x^41 + 62*x^40 + 74*x^39 + 60*x^38 + 33*x^37 + 111*x^36 + 67*x^35 + 64*x^34 + 75*x^33 + 65*x^32 + 33*x^31 + 121*x^30 + 108*x^29 + 111*x^28 + 80*x^27 + 95*x^26 + 99*x^25 + 49*x^24 + 109*x^23 + 111*x^22 + 116*x^21 + 79*x^20 + 108*x^19 + 99*x^18 + 121*x^17 + 67*x^16 + 95*x^15 + 119*x^14 + 48*x^13 + 110*x^12 + 75*x^11 + 95*x^10 + 89*x^9 + 49*x^8 + 49*x^7 + 52*x^6 + 64*x^5 + 82*x^4 + 95*x^3 + 117*x^2 + 48*x + 89
AA = A.coefficient()
flag = ''
for i in range(len(AA)):
flag += chr(AA[i])
print(flag)
can_you_guess_me
造格解决，求出t，转换为hnp问题。
from Crypto.Util.number import *
import gmpy2
n = 5
T = 2**48
E = 2**32
q = 313199526393254794805899275326380083313
a = [258948702106389340127909287396807150259, 130878573261697415793888397911168583971, 287085364108707601156242002650192970665, 172240654236516299340495055728541554805, 206056586779420225992168537876290239524]
m = matrix(ZZ,6,6)
for i in range(5):
m[i,-1] = a[i]
m[i,i] = 1
m[-1,-1] = q
M = m.LLL()
T_ = []
for i in range(6):
T_1 = []
for j in range(5):
T_1.append(M[i,j])
T_.append(T_1)
# print(T_)
result1=matrix(ZZ,T_[:-2]).right_kernel()
t = result1.basis()
# print(t)
t = [70461467654746, 7976473815457, 179142956465832, 176554799971356, 145182873667321]
bound = 2 ^ 32
HNP = matrix(QQ,7,7)
for i in range(5):
HNP[i,i] = q
HNP[-2,i] = t[i]
HNP[-1,i] = -a[i]
HNP[-2,-2] = bound/q
HNP[-1,-1] = bound
m_final = HNP.LLL()
# print(m_final)
for line in m_final:
if(line[-1] == bound):
print(line)
# for i in range(7):
# print(int(m_final[i,-2]*q)//2^128 % q)
# print(m_final*HNP^(-1))
a = [258948702106389340127909287396807150259, 130878573261697415793888397911168583971, 287085364108707601156242002650192970665, 172240654236516299340495055728541554805, 206056586779420225992168537876290239524]
t = [70461467654746, 7976473815457, 179142956465832, 176554799971356, 145182873667321]
e = [1207385170, 2227664800, 194948058, 2380502097, 893798212]
flag = int(61832802753575197703139019131565944821482782720/313199526393254794805899275326380083313 * q /bound)
print(flag)
print(hex(flag))
assert((t[1] * flag - e[1])%q == a[1])