糖醋小鸡块的blog
0%

Crypto趣题-后量子密码

发表于 分类于 Valine：

该文章主要记录一些后量子密码相关的趣题

sound

题目来源：暂不明确

题目：

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
81
82
83
84
85
86
87
88
89
import numpy as np
from numpy.polynomial import polynomial as poly
from Crypto.Util.number import *
# from secert import flag

def poly_mul(x, y, z, poly_mod):

  init_poly = poly.polymul(x, y)
  res_poly = poly.polydiv(init_poly % z, poly_mod)[1] % z

  return np.int64(np.round(res_poly))


def poly_add(x, y, z, poly_mod):

  init_poly = poly.polyadd(x, y)
  res_poly = poly.polydiv(init_poly % z, poly_mod)[1] % z

  return np.int64(np.round(res_poly))

def r2_distribution(len):

  return np.random.randint(0, 2, len, dtype=np.int64)

def rz_distribution(z, len):

  return np.random.randint(0, z, len, dtype=np.int64)

def gass_distribution(len):

  return np.int64(np.random.normal(0, 2, size=len))

def keygen(len, z, poly_mod):

  s = r2_distribution(len)
  a = rz_distribution(z, len)
  e = gass_distribution(len)
  b = poly_add(poly_mul(-a, s, z, poly_mod), -e, z, poly_mod)

  key = [a, b, s]

  return key


def encrypt(key, lent, q, t, poly_mod, message):
    lm = []
    mg = hex(message)[2:]
    for i in range(0, len(mg)):
        lm.append(ord(mg[i]))

    m = np.array(lm + [0] * (lent - len(lm)), dtype=np.int64) % t
    delta = q // t
    delta_m = delta * m % q
    e1 = gass_distribution(lent)
    e2 = gass_distribution(lent)
    u = r2_distribution(lent)
    a = key[0]
    b = key[1]
    c0 = poly_add(poly_add(poly_mul(b, u, q, poly_mod), e1, q, poly_mod), delta_m, q, poly_mod)
    c1 = poly_add(poly_mul(a, u, q, poly_mod), e2, q, poly_mod)

    c = [c0, c1]

    return c


n = 128
q = 2**60
t = 2**32
poly_mod = np.array([1] + [0] * (n - 1) + [1])
key = keygen(n, q, poly_mod)
print(key)
# m = bytes_to_long("test")
# c = encrypt(key, n, q, t, poly_mod, m)
# print("c0 =", c[0].tolist())
# print("c1 =", c[1].tolist())
# print("a =", key[0].tolist())
# print("b =", key[1].tolist())
# print("s =", key[2].tolist())

'''

c0 = [561582066946621440, 817928620285456128, 42443557674760704, 394102843794633984, 72227332717773568, 670192568490572288, 1124338053013283584, 280137744525874176, 63888555088669696, 208355146401743872, 301595565562120704, 50991331858064384, 686628375362950656, 584548366308243456, 1133668516727752192, 474240047688777728, 985154171217232384, 501564712591768576, 914588095025884160, 746830802337096704, 459209143204393984, 603634479787543552, 69069089375354880, 473248420863702016, 754603248638489600, 883576336602057728, 644743636485886976, 319901457654988800, 89793303522564096, 1090071466212856832, 369690536666460160, 1082593341867948032, 441359938321465344, 496386518207440896, 863575421687413760, 811516483959451648, 205996965699836928, 170811895655694336, 335832012272743424, 402108133996681216, 222897130593269760, 317187616437233664, 202919598933315584, 750395341955145728, 366873741733378048, 117730747288055808, 298767968401977344, 923270470424109056, 1076698083295752192, 926422812303050752, 216450081157644288, 981499274968659968, 349655761329862656, 557140442005530624, 858566688669024256, 1149813151825131520, 553370166035001344, 493722732465334272, 732590954557634560, 1052906163890288640, 1021790009160361984, 796011853108049920, 978483522580508672, 894955797433884672, 203559391733489664, 1062410754780596224, 452371485913219072, 651736133029277696, 313976115776903168, 31756099628290048, 71787963926824960, 1109713454413903872, 1112298691994664960, 539132530906077184, 435437107964127232, 833705546252720128, 928849583016886272, 526205130688186368, 1121288102191632384, 536933088453670912, 924962525849556992, 241106313851269120, 717238131918897152, 452642326250387456, 354673268076457984, 16428317258336256, 1061713751710105600, 1139952509444370432, 146561032291504128, 944139817563172864, 670119880592367616, 424458702156075008, 26734611035709440, 552311974354061312, 252009367779129344, 362515232289822720, 942674829586386944, 444916638598115328, 931633333648844800, 54609902697099264, 831316650858829824, 113431421994166272, 907245098202316800, 89326594807300096, 1016570475364521984, 175954756550047744, 53317212366995456, 49595714294925312, 490302383520435200, 260454924258463744, 713597063793843200, 759813046691484672, 491213271622251520, 861532845783883776, 1001029896578621440, 1017093991719427072, 901303193624896512, 85708980918313472, 1094723859831225856, 978173121944355840, 1074912611780537344, 816683396743236608, 406912122093641728, 326181480111288320, 644075764054597632, 114416502291357696, 543109737210728448, 311623753071517696]
c1 = [91790686412574976, 744110810763883904, 864964412801026560, 548689841412167296, 740051294265845504, 57902427994320256, 1068935585666797056, 625707146907438848, 551559740589006848, 233440834921673728, 108552546335437312, 166310503165480448, 267060328550531584, 735758245725702656, 712188529675013632, 386374530222726144, 823764165634433536, 123823217368593408, 1004488834478358528, 177477850679225344, 882498511506926592, 5562190320664577, 1106414131124581376, 327516552070835200, 1028475201394497536, 847983498883162112, 1095687065391010816, 706624008349679616, 204676471898160128, 926864853752850432, 152748692869394432, 326128165710331904, 237842086203092992, 1057799799477599232, 345130623233955840, 790672249565697024, 523310000234446848, 840615312867051520, 924979087214993408, 979878291879419904, 115424422845719552, 884924921252442112, 579700963339163648, 1097673093701288960, 704450636638808064, 556078232166107136, 600772693891751936, 905676852758437888, 33621101477464064, 962348719049031680, 925511116990984192, 722520866171662336, 84706802559584256, 530104859095961600, 586276707214465024, 1037552671549552640, 47697269444673536, 210690498450145280, 65070464261654528, 550494166683250688, 777902097764929536, 490832146778818560, 229195607527737344, 767464696299196416, 237315984854040576, 836604288237121536, 507968614131243008, 1146549269233274880, 947811005289312256, 415029326696218624, 73794452197351424, 1111805188636655616, 574425125131241472, 1077883538301097984, 1093417286225403904, 860646266870226944, 238318354083344384, 200921121541777408, 896691473408880640, 794971973394204672, 128454122568243200, 1048391326124871680, 811035464481740800, 922934079239356416, 1033337101914234880, 253445566297591808, 820899412762693632, 51737950452322304, 115554283493984256, 1013231171511318528, 887144973891745792, 903483706965391360, 1100501053366775808, 691065365527990272, 265415356256839680, 969461346065672192, 719496129535698944, 177295085227089920, 860427351595780096, 125812051803891712, 852658796584968192, 487770283774704640, 1070758201904617472, 696983558330196992, 911281563710520320, 676402547272127488, 240686574930634752, 412323376183429120, 619325898981327872, 551028995171842048, 124379235049986048, 649110127901071360, 453922531021119488, 1022481642604582912, 637680606991188992, 51749356430436352, 388350126415356928, 335267552976254464, 960188628024263168, 1088514924986558976, 1094423617550431488, 451833526251570688, 870461009339176704, 697351158038040832, 536089791190207360, 1118146398557536256, 518612046112251904, 241398597936840704]
a = [219983724512243970, 752269838678521187, 480509403910281428, 133185208045420765, 490932722804543133, 372886136396692359, 354557330633882122, 678374399146208018, 960245804475102275, 806115518790255556, 828442613098615970, 544833163224524043, 101022959319030935, 117082421755238805, 461182355875216799, 1056119810024896502, 1082000166040876591, 738717114032361767, 578460771662302172, 21556920074594644, 708384954866463679, 1128876901552996333, 874708202228666633, 1092990784029535155, 705415640472089353, 29671570923717836, 386333436179138094, 279081567858606603, 358852578576320987, 847350768179480795, 817603347707592640, 378977756047386392, 201769345485693076, 1063632060034171765, 1015775208741323787, 365127265851837110, 895275437758090601, 901913451551062231, 86419657119953320, 1149882820426142461, 157964525788076127, 631235061398583563, 470949966047613817, 180994349394944987, 228238609714444899, 73624200469844200, 521149905985689963, 19697681380014322, 233461826565515880, 891353264527116993, 1132362343348330909, 719302772676639611, 816690530086729127, 612858319654028202, 1029240232500231324, 266903296429217560, 66793172770160368, 836559325488504608, 1112595888239841739, 1115401337078198049, 261716078450833148, 235662011088480216, 24855917687216082, 619578281956001818, 589359800577838713, 780827177034370452, 62331996978291742, 757201723755709445, 325754948905836705, 298782045417610682, 958766007892311371, 474147826024027639, 1070490722277174646, 190459580153148093, 575005416421018885, 1120664053122918701, 982594533717886793, 252358471190638150, 869750160966337040, 1014322228871199234, 665558545558521628, 105433885394318337, 377027901347400638, 858616841227650075, 1043520529148794434, 1011002490399424434, 207664442877510988, 871194434207030706, 43210520355326250, 602232789264907632, 474051046305769969, 184712552380050689, 795080413713622552, 69957213032924047, 528473007846250043, 169221743016746138, 455880753546244419, 329225658406843642, 1150659098485422471, 626876298585651008, 490793379497608670, 933534706184661647, 467052917787037730, 1075596724935302342, 633000416730524162, 1090163205445120705, 72568659182243843, 571233962016655997, 1038522694640247261, 1025630622605696194, 553753007953333627, 231471906689387866, 558788723869154294, 673804202648107772, 232283327890481849, 39742925179368561, 135909458983766175, 192124298319965985, 839263496419016075, 162231894553173376, 661693215639557019, 655784289160683355, 1062416543453873451, 319938129595811007, 1002025365666496902, 272017768612866462, 482130564327357100, 982163056351966292]
b = [820893636450185216, 1088723008695521024, 563505788571372160, 225792174390707712, 531991982654429312, 676436714054308864, 74314379213871872, 78960436919170688, 744901196366641920, 556510129527018752, 71967857250009600, 714820946954724352, 1047939442957058048, 475133098260006400, 764020773208596992, 495337689359947776, 969475874903125504, 132719289181729792, 301591784012423168, 886113347782835200, 477381121894258688, 843499387721308160, 508541992967101440, 135898603458110464, 373248303372987392, 696522694584843264, 22397882759483392, 867189773938512896, 231922357411858432, 452886634658905088, 337138259452950528, 246330467020038144, 336880752906045440, 712110254503864320, 1109022090563764224, 736941976050098176, 340820746543463424, 319152585759258624, 627473838419951616, 724549720670470144, 941976447076147200, 284306369459089408, 474986938990024704, 169392264058798080, 425082943668336640, 780502226419180544, 534812953559536640, 307991466712799232, 256772641512932352, 954565062645100544, 642433129475169280, 554579429440409600, 492586567437330432, 504243514518411264, 559583345168955392, 1047970717391220736, 354007966625097728, 944087368508420096, 48593600443238400, 412546108591775744, 371798716943661056, 109603610083078144, 912962403831732224, 493593202496430080, 435411737100828672, 416258656632209408, 41271759105748992, 547450588221173760, 1019985813100816384, 1133270880179824640, 416184705628168192, 1002938666972422144, 131467088438026240, 730507494540156928, 1122116292811296768, 179931222600130560, 704668788433995776, 693568343631073280, 159315312318967808, 228151058164389888, 78591434106697728, 1101441417145767936, 1011500470535821312, 103335769958184960, 723984495516817408, 421553904096403456, 1009636649059076096, 880471059436941312, 1017699541008359424, 880891531629418496, 1001214838765556736, 584549630850997248, 63724037422592000, 984435711617449984, 737723590588489728, 235901319105159168, 867142310717528064, 62598429756019712, 135623731618318336, 103508320292760576, 714343001741491200, 384031562306680832, 620521749068774400, 562199194838183936, 137440949282672640, 105902179785320448, 76984505248291840, 81968680790070272, 932887350172256256, 162426306785337344, 248707672736583680, 338911851801801216, 664174993098860032, 590418449833950720, 668934689108922112, 1050363471682760704, 627510981430159872, 157201265188110848, 332191804534742528, 610005938211220480, 789419961205813248, 350516436368000512, 135054071035246848, 1103634020293607168, 851221988945015936, 339941701245870080, 810615510791110656, 1139102409849577472]
s = [0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0]

'''

题目给的函数有点多，先理清每个函数具体作用是什么：

分析函数

poly_mul
1
2
3
4
5
6
def poly_mul(x, y, z, poly_mod):

  init_poly = poly.polymul(x, y)
  res_poly = poly.polydiv(init_poly % z, poly_mod)[1] % z

  return np.int64(np.round(res_poly))

输入：

  • x、y：多项式系数列表
  • z：模数
  • poly_mod：模多项式系数列表

具体来说，该函数实现x、y多项式相乘后，每项系数模z，再将整个多项式模poly_mod。

poly_add
1
2
3
4
5
6
def poly_add(x, y, z, poly_mod):

  init_poly = poly.polyadd(x, y)
  res_poly = poly.polydiv(init_poly % z, poly_mod)[1] % z

  return np.int64(np.round(res_poly))

这个函数的输入参数列表与poly_add完全一样，它实现的是x、y多项式相加后，每项系数模z，再将整个多项式模poly_mod。

r2_distribution
1
2
3
def r2_distribution(len):

  return np.random.randint(0, 2, len, dtype=np.int64)

该函数生成一个长度为len，元素为0或1的随机数列表

rz_distribution
1
2
3
def rz_distribution(z, len):

  return np.random.randint(0, z, len, dtype=np.int64)

该函数生成一个长度为len，元素为0-z之间的随机数列表

gass_distribution
1
2
3
def gass_distribution(len):

  return np.int64(np.random.normal(0, 2, size=len))

该函数返回一个长度为len，随机数从给定正态分布中抽取的列表，各个参数意义详见：

numpy.random.normal详解-CSDN博客

自己测试一下就可以知道，其实可以认为他就是一个小噪声：

1
2
3
4
length = 128
print(gass_distribution(length))

[-1  0 -1  2  0  1  2  1  0  0  0  0  1 -4  0  0 -1  3  2 -1 -1  2  0  0 -1  3  2  1  0  1  0 -2 -2  3 -1  3 -4 -1 -1  0  1  0 -3 -3  2  2  0 -4 0  0  0  0  0 -1 -1 -1  0 -2  0  0 -2  0  0  0  1 -1  0  0 -2  2  0  1 -1  2  2 -3  0 -1  3  1 -2 -2  0  0  0 -1  4  2  2 -1  0 -1  4 -1  1  0 0 -1 -1  0  0  3  0  1 -3 -1  0 -1  1  2  0  1 -1 -1 -2 -1  0 -1 -1  1 2  0  3 -1  1  0 -2  1]

以上就是五个加密需要用到的基本函数，总结一下，其实他就是定义了一个多项式的商环，运算也均在这个商环上进行。而这些随机生成的列表，也就可以看作是这个商环上的多项式系数列表，这个商环如下：

其中，f(x)就是题目中的poly_mod，Zq[x]指模q下的多项式环。

那么从这里开始，本文后续的多项式运算都定义在该商环上。

再看keygen函数，就可以知道几个多项式的关系：

其中，s的系数均为0或1，e的系数为一个正态分布的小噪声，而a、b的系数则应该是由较大的数构成的。

然后对于encrypt函数，其加密流程如下：

  • 把flag转为十六进制字符串，然后把每个十六进制字符转为ASCII码，然后在后面填充足够的0使得m也是一个同长度的多项式系数列表(这些东西自己生成数据测试一下就明白了)
  • 定义一个较大的数delta，题目中是2^28，然后将m的多项式系数乘delta。这里就可以想到，对于m来说，只有前面非0的部分乘上了delta而显著变大，后面的填充0是不变的
  • 生成两个满足正态分布的小噪声e1、e2，再生成一个系数均为0或1的随机临时密钥u，计算下面两个多项式作为密文并返回(其中dm表示乘上了delta的m系数列表)：

那么加密流程就分析完了，接下来进入解密。

解密

其实见过的话，差不多就能反应过来这其实是RLWE加密，而题目实现的其实就是RLWE的标准加密过程，具体可以参考：

格密码之Ring-LWE (section 1) - 知乎 (zhihu.com)

了解了加解密流程的话，会发现其实这个题目已经给好了我们私钥s，而有了私钥s我们就可以用如下方式解密(为了表示方便，多项式后面就不写(x)了)：

由于有：

所以：

也就是：

可以发现，后面的(eu+e1+se2)仍然是个小噪声，因此我们直接对(c0 + s*c1)模delta，就能得到m。然后有一点需要注意，噪声(eu+e1+se2)可能有负值，而为负值的时候，模delta会导致最终结果小1，需要对应添加回去。

exp：

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import numpy as np
from numpy.polynomial import polynomial as poly
from Crypto.Util.number import *
# from secert import flag

def poly_mul(x, y, z, poly_mod):

  init_poly = poly.polymul(x, y)
  res_poly = poly.polydiv(init_poly % z, poly_mod)[1] % z

  return np.int64(np.round(res_poly))


def poly_add(x, y, z, poly_mod):

  init_poly = poly.polyadd(x, y)
  res_poly = poly.polydiv(init_poly % z, poly_mod)[1] % z

  return np.int64(np.round(res_poly))

def r2_distribution(len):

  return np.random.randint(0, 2, len, dtype=np.int64)

def rz_distribution(z, len):

  return np.random.randint(0, z, len, dtype=np.int64)

def gass_distribution(len):

  return np.int64(np.random.normal(0, 2, size=len))

def keygen(len, z, poly_mod):

  s = r2_distribution(len)
  a = rz_distribution(z, len)
  e = gass_distribution(len)
  b = poly_add(poly_mul(-a, s, z, poly_mod), -e, z, poly_mod)

  key = [a, b, s]

  return key


def encrypt(key, lent, q, t, poly_mod, message):
    lm = []
    mg = hex(message)[2:]
    for i in range(0, len(mg)):
        lm.append(ord(mg[i]))

    m = np.array(lm + [0] * (lent - len(lm)), dtype=np.int64) % t
    delta = q // t
    delta_m = delta * m % q
    e1 = gass_distribution(lent)
    e2 = gass_distribution(lent)
    u = r2_distribution(lent)
    a = key[0]
    b = key[1]
    c0 = poly_add(poly_add(poly_mul(b, u, q, poly_mod), e1, q, poly_mod), delta_m, q, poly_mod)
    c1 = poly_add(poly_mul(a, u, q, poly_mod), e2, q, poly_mod)

    c = [c0, c1]

    return c

n = 128
q = 2**60
t = 2**32
poly_mod = np.array([1] + [0] * (n - 1) + [1])

c0 = [561582066946621440, 817928620285456128, 42443557674760704, 394102843794633984, 72227332717773568, 670192568490572288, 1124338053013283584, 280137744525874176, 63888555088669696, 208355146401743872, 301595565562120704, 50991331858064384, 686628375362950656, 584548366308243456, 1133668516727752192, 474240047688777728, 985154171217232384, 501564712591768576, 914588095025884160, 746830802337096704, 459209143204393984, 603634479787543552, 69069089375354880, 473248420863702016, 754603248638489600, 883576336602057728, 644743636485886976, 319901457654988800, 89793303522564096, 1090071466212856832, 369690536666460160, 1082593341867948032, 441359938321465344, 496386518207440896, 863575421687413760, 811516483959451648, 205996965699836928, 170811895655694336, 335832012272743424, 402108133996681216, 222897130593269760, 317187616437233664, 202919598933315584, 750395341955145728, 366873741733378048, 117730747288055808, 298767968401977344, 923270470424109056, 1076698083295752192, 926422812303050752, 216450081157644288, 981499274968659968, 349655761329862656, 557140442005530624, 858566688669024256, 1149813151825131520, 553370166035001344, 493722732465334272, 732590954557634560, 1052906163890288640, 1021790009160361984, 796011853108049920, 978483522580508672, 894955797433884672, 203559391733489664, 1062410754780596224, 452371485913219072, 651736133029277696, 313976115776903168, 31756099628290048, 71787963926824960, 1109713454413903872, 1112298691994664960, 539132530906077184, 435437107964127232, 833705546252720128, 928849583016886272, 526205130688186368, 1121288102191632384, 536933088453670912, 924962525849556992, 241106313851269120, 717238131918897152, 452642326250387456, 354673268076457984, 16428317258336256, 1061713751710105600, 1139952509444370432, 146561032291504128, 944139817563172864, 670119880592367616, 424458702156075008, 26734611035709440, 552311974354061312, 252009367779129344, 362515232289822720, 942674829586386944, 444916638598115328, 931633333648844800, 54609902697099264, 831316650858829824, 113431421994166272, 907245098202316800, 89326594807300096, 1016570475364521984, 175954756550047744, 53317212366995456, 49595714294925312, 490302383520435200, 260454924258463744, 713597063793843200, 759813046691484672, 491213271622251520, 861532845783883776, 1001029896578621440, 1017093991719427072, 901303193624896512, 85708980918313472, 1094723859831225856, 978173121944355840, 1074912611780537344, 816683396743236608, 406912122093641728, 326181480111288320, 644075764054597632, 114416502291357696, 543109737210728448, 311623753071517696]
c1 = [91790686412574976, 744110810763883904, 864964412801026560, 548689841412167296, 740051294265845504, 57902427994320256, 1068935585666797056, 625707146907438848, 551559740589006848, 233440834921673728, 108552546335437312, 166310503165480448, 267060328550531584, 735758245725702656, 712188529675013632, 386374530222726144, 823764165634433536, 123823217368593408, 1004488834478358528, 177477850679225344, 882498511506926592, 5562190320664577, 1106414131124581376, 327516552070835200, 1028475201394497536, 847983498883162112, 1095687065391010816, 706624008349679616, 204676471898160128, 926864853752850432, 152748692869394432, 326128165710331904, 237842086203092992, 1057799799477599232, 345130623233955840, 790672249565697024, 523310000234446848, 840615312867051520, 924979087214993408, 979878291879419904, 115424422845719552, 884924921252442112, 579700963339163648, 1097673093701288960, 704450636638808064, 556078232166107136, 600772693891751936, 905676852758437888, 33621101477464064, 962348719049031680, 925511116990984192, 722520866171662336, 84706802559584256, 530104859095961600, 586276707214465024, 1037552671549552640, 47697269444673536, 210690498450145280, 65070464261654528, 550494166683250688, 777902097764929536, 490832146778818560, 229195607527737344, 767464696299196416, 237315984854040576, 836604288237121536, 507968614131243008, 1146549269233274880, 947811005289312256, 415029326696218624, 73794452197351424, 1111805188636655616, 574425125131241472, 1077883538301097984, 1093417286225403904, 860646266870226944, 238318354083344384, 200921121541777408, 896691473408880640, 794971973394204672, 128454122568243200, 1048391326124871680, 811035464481740800, 922934079239356416, 1033337101914234880, 253445566297591808, 820899412762693632, 51737950452322304, 115554283493984256, 1013231171511318528, 887144973891745792, 903483706965391360, 1100501053366775808, 691065365527990272, 265415356256839680, 969461346065672192, 719496129535698944, 177295085227089920, 860427351595780096, 125812051803891712, 852658796584968192, 487770283774704640, 1070758201904617472, 696983558330196992, 911281563710520320, 676402547272127488, 240686574930634752, 412323376183429120, 619325898981327872, 551028995171842048, 124379235049986048, 649110127901071360, 453922531021119488, 1022481642604582912, 637680606991188992, 51749356430436352, 388350126415356928, 335267552976254464, 960188628024263168, 1088514924986558976, 1094423617550431488, 451833526251570688, 870461009339176704, 697351158038040832, 536089791190207360, 1118146398557536256, 518612046112251904, 241398597936840704]
a = [219983724512243970, 752269838678521187, 480509403910281428, 133185208045420765, 490932722804543133, 372886136396692359, 354557330633882122, 678374399146208018, 960245804475102275, 806115518790255556, 828442613098615970, 544833163224524043, 101022959319030935, 117082421755238805, 461182355875216799, 1056119810024896502, 1082000166040876591, 738717114032361767, 578460771662302172, 21556920074594644, 708384954866463679, 1128876901552996333, 874708202228666633, 1092990784029535155, 705415640472089353, 29671570923717836, 386333436179138094, 279081567858606603, 358852578576320987, 847350768179480795, 817603347707592640, 378977756047386392, 201769345485693076, 1063632060034171765, 1015775208741323787, 365127265851837110, 895275437758090601, 901913451551062231, 86419657119953320, 1149882820426142461, 157964525788076127, 631235061398583563, 470949966047613817, 180994349394944987, 228238609714444899, 73624200469844200, 521149905985689963, 19697681380014322, 233461826565515880, 891353264527116993, 1132362343348330909, 719302772676639611, 816690530086729127, 612858319654028202, 1029240232500231324, 266903296429217560, 66793172770160368, 836559325488504608, 1112595888239841739, 1115401337078198049, 261716078450833148, 235662011088480216, 24855917687216082, 619578281956001818, 589359800577838713, 780827177034370452, 62331996978291742, 757201723755709445, 325754948905836705, 298782045417610682, 958766007892311371, 474147826024027639, 1070490722277174646, 190459580153148093, 575005416421018885, 1120664053122918701, 982594533717886793, 252358471190638150, 869750160966337040, 1014322228871199234, 665558545558521628, 105433885394318337, 377027901347400638, 858616841227650075, 1043520529148794434, 1011002490399424434, 207664442877510988, 871194434207030706, 43210520355326250, 602232789264907632, 474051046305769969, 184712552380050689, 795080413713622552, 69957213032924047, 528473007846250043, 169221743016746138, 455880753546244419, 329225658406843642, 1150659098485422471, 626876298585651008, 490793379497608670, 933534706184661647, 467052917787037730, 1075596724935302342, 633000416730524162, 1090163205445120705, 72568659182243843, 571233962016655997, 1038522694640247261, 1025630622605696194, 553753007953333627, 231471906689387866, 558788723869154294, 673804202648107772, 232283327890481849, 39742925179368561, 135909458983766175, 192124298319965985, 839263496419016075, 162231894553173376, 661693215639557019, 655784289160683355, 1062416543453873451, 319938129595811007, 1002025365666496902, 272017768612866462, 482130564327357100, 982163056351966292]
b = [820893636450185216, 1088723008695521024, 563505788571372160, 225792174390707712, 531991982654429312, 676436714054308864, 74314379213871872, 78960436919170688, 744901196366641920, 556510129527018752, 71967857250009600, 714820946954724352, 1047939442957058048, 475133098260006400, 764020773208596992, 495337689359947776, 969475874903125504, 132719289181729792, 301591784012423168, 886113347782835200, 477381121894258688, 843499387721308160, 508541992967101440, 135898603458110464, 373248303372987392, 696522694584843264, 22397882759483392, 867189773938512896, 231922357411858432, 452886634658905088, 337138259452950528, 246330467020038144, 336880752906045440, 712110254503864320, 1109022090563764224, 736941976050098176, 340820746543463424, 319152585759258624, 627473838419951616, 724549720670470144, 941976447076147200, 284306369459089408, 474986938990024704, 169392264058798080, 425082943668336640, 780502226419180544, 534812953559536640, 307991466712799232, 256772641512932352, 954565062645100544, 642433129475169280, 554579429440409600, 492586567437330432, 504243514518411264, 559583345168955392, 1047970717391220736, 354007966625097728, 944087368508420096, 48593600443238400, 412546108591775744, 371798716943661056, 109603610083078144, 912962403831732224, 493593202496430080, 435411737100828672, 416258656632209408, 41271759105748992, 547450588221173760, 1019985813100816384, 1133270880179824640, 416184705628168192, 1002938666972422144, 131467088438026240, 730507494540156928, 1122116292811296768, 179931222600130560, 704668788433995776, 693568343631073280, 159315312318967808, 228151058164389888, 78591434106697728, 1101441417145767936, 1011500470535821312, 103335769958184960, 723984495516817408, 421553904096403456, 1009636649059076096, 880471059436941312, 1017699541008359424, 880891531629418496, 1001214838765556736, 584549630850997248, 63724037422592000, 984435711617449984, 737723590588489728, 235901319105159168, 867142310717528064, 62598429756019712, 135623731618318336, 103508320292760576, 714343001741491200, 384031562306680832, 620521749068774400, 562199194838183936, 137440949282672640, 105902179785320448, 76984505248291840, 81968680790070272, 932887350172256256, 162426306785337344, 248707672736583680, 338911851801801216, 664174993098860032, 590418449833950720, 668934689108922112, 1050363471682760704, 627510981430159872, 157201265188110848, 332191804534742528, 610005938211220480, 789419961205813248, 350516436368000512, 135054071035246848, 1103634020293607168, 851221988945015936, 339941701245870080, 810615510791110656, 1139102409849577472]
s = [0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0]

_c1 = [0 for i in range(len(c1))]
for i in range(len(c1)):
   _c1[i] = (q - c1[i]) % q
final = poly_add(c0 , poly_mul(s, c1, q, poly_mod), q, poly_mod)

temp = (final//(2**28))[:76]
temp1 = (final%(2**28))[:76]

c = ""
for i in range(len(temp)):
  if(temp1[i] > 100000):
    c += chr(temp[i]+1)
  else:
    c += chr(temp[i])

print(long_to_bytes(int(c,16)))

#flag{32fd349072a04dab71a3f2c78e24b9c0}