Gaston La Paffe
Gaston a fabriqué des signatures à partir de ce module
import numpy as np
from Crypto.Random.random import randint, choice
from Crypto.Hash import SHA512, SHA256
from Crypto.Util.number import bytes_to_long
Q = 8383489
B = 16384
N = 512
class Server:
def __init__(self, Q, B, N):
self.Q = Q
self.B = B
self.N = N
self.a = [randint(0, Q - 1) for _ in range(self.N)]
self.__s1 = [randint(-1, 1) % Q for _ in range(self.N)]
self.__s2 = [randint(-1, 1) % Q for _ in range(self.N)]
self.t = self.poly_mul_add(self.a, self.__s1, self.__s2)
def sk(self):
return self.__s1, self.__s2
def pk(self):
return self.a, self.t
def H(self, v1, m):
h = bytes_to_long(SHA512.new(str(v1).encode() + m).digest())
h = list(map(int, list(f"{h:0512b}")))
return h
def poly_add(self, p1, p2):
return [ (p1[i] + p2[i]) % self.Q for i in range(self.N) ]
def poly_sub(self, p1, p2):
return [ (p1[i] - p2[i]) % self.Q for i in range(self.N) ]
def poly_mul_add(self, p1, p2, p3):
return self.poly_add(self.poly_mul(p1, p2), p3)
def poly_mul(self, p1,p2):
res = np.convolve(p1, p2)
res = [0] * (2 * self.N - 1 - len(res)) + list(res)
a = list(map(int, res[:self.N]))
b = list(map(int, res[self.N:] + [0]))
res = self.poly_sub(a, b)
return res
def reject(self, z):
for v in z:
if v > self.B and v < self.Q - self.B:
return True
return False
def sign(self, m):
while True:
y1 = [ randint(-self.B, self.B) % self.Q for _ in range(self.N) ]
y2 = [ randint(-self.B, self.B) % self.Q for _ in range(self.N) ]
h = self.poly_mul_add(self.a, y1, y2)
c = self.H(h, m)
z1 = self.poly_mul_add(self.__s1, c, y1)
z2 = self.poly_mul_add(self.__s2, c, y2)
if self.reject(z1) or self.reject(z2):
continue
return y1, z1, z2, c
def verify(self, z1, z2, c, m):
if self.reject(z1) or self.reject(z2):
return False
temp1 = self.poly_mul_add(self.a, z1, z2)
temp2 = self.poly_mul(self.t, c)
h = self.poly_sub(temp1, temp2)
c_prime = self.H(h, m)
return c == c_prime
def get_random_string(length):
return ''.join(choice(string.ascii_letters) for _ in range(length))
if __name__ == "__main__":
server = Server(Q, B, N)
a, t = server.pk()
print(json.dumps({
"a": a,
"t": t,
}))
data = []
for i in range(N):
message = get_random_string(20)
y1, z1, z2, c = server.sign(message.encode())
assert server.verify(z1, z2, c, message.encode()), "Error: verification error."
data.append({
"message": message,
"z1": z1,
"z2": z2,
"c": c,
"y1": y1,
})
print(json.dumps(data))
flag = open("flag.txt", "rb").read()
s1, s2 = server.sk()
key = SHA256.new(str(s1).encode() + str(s2).encode()).digest()
iv = os.urandom(16)
E = AES.new(key, AES.MODE_CBC, iv = iv)
enc = E.encrypt(pad(flag, 16))
print(json.dumps({
"iv": iv.hex(),
"enc": enc.hex()
}))
Il faut retrouver le flag à partir de la sortie.
Contexte mathématique
Les noms des fonctions semblent indiquer qu’on est dans des polynômes modulo Q=8383489.
La fonction de multiplication est un peu étrange: le résultat de la convolution est rempli avec des zéros à gauche. Donc les polynômes sont rangés comme ceci:
polynôme: an X^N + ... + a1 + a0
p = [aN, ..., a1, a0]
Dans la fonction poly_mul on a aussi un zéro ajouté à la fin de b. Mathématiquement, cette fonction réalise donc: p1 * p2 * -X modulo X^N+1
Méthode de signature
On fixe:
- des polynômes secrets S1 et S2
- un polynôme public aléatoire A
- un polynôme public T = mul(A,S1) + S2
Pour une signature d’un message m on calcule:
- deux polynômes aléatoires Y1, Y2 modulo Q
- un sel
str(mul(A,Y1)+Y2)(dont le format n’est pas très important) - un hash c=SHA512(sel + m) vu comme un polynôme à coefficients 0 ou 1
- on calcule
Z1 = mul(S1, c)+Y1etZ2 = mul(S2, c)+Y2 - on publie Y1, Z1, Z2, c
Il n’est pas nécessaire d’utiliser Y2 ni les secrets pour vérifier la signature puisque mul(A, Z1) + Z2 = mul(T, c) + mul(A, Y1) + Y2.
On calcule donc mul(A, Z1) + Z2 - mul(T, c) = salt qui doit donner le bon hash.
La gaffe
Regardons les équations et voyons si on peut extraire un secret. Puisqu’on a Y1, Z1, c la formule Z1 = mul(S1, c)+Y1 permet de retrouver S1.
Il suffit de calculer: S1 = (Z1 - Y1) / (c * -X) = (Z1 - Y1) / c * X^511
La difficulté est dans le calcul de l’inverse de c.
On peut utiliser SAGE si on ne sait pas comment faire en pratique, en utilisant la formule de Bézout:
from sage.all import Zmod
Q = 8383489
N = 512
Zq = Zmod(Q)
R = Zq["x"]
x = R.an_element()
Cyclo = x**N + 1
def inverse(c):
# u*Cyclo + c*cinv = 1
gcd, u, cinv = Cyclo.xgcd(c)
assert gcd == 1
return cinv
Solution
Une fois qu’on a calculé S1 par la méthode précédente, on calcule simplement s2 = poly_sub(t, poly_mul(a, s1))
On peut alors déchiffrer le message:
# Les données
import json
with open("output.txt") as f:
pub = json.loads(next(f))
sigs = json.loads(next(f))
crypt = json.loads(next(f))
sig = sigs[0] # une seule suffit
t, a = pub["t"], pub["a"]
# Fonctions
import numpy
def poly_add(p1, p2):
return [(p1[i] + p2[i]) % Q for i in range(N)]
def poly_sub(p1, p2):
return [(p1[i] - p2[i]) % Q for i in range(N)]
def mul(p1, p2):
res = numpy.convolve(p1, p2)
res = [0] * (2 * N - len(res)) + list(res)
hi = list(map(int, res[:N]))
lo = list(map(int, res[N:]))
res = poly_sub(lo, hi)
return res
# Un peu d'algèbre
from sage.all import Zmod
Q = 8383489
N = 512
Zq = Zmod(Q)
R = Zq["x"]
x = R.an_element()
cyclo = x**512 + 1
def inverse(c):
poly = sum([k * x ** (N - 1 - i) for i, k in enumerate(c)])
pgcd, _, pinv = cyclo.xgcd(poly)
coef = pinv.coefficients(sparse=False)
if len(coef) < N:
coef += (N - len(coef)) * [0]
return [int(x) for x in reversed(coef)]
# La solution
y1 = sig["y1"]
z1 = sig["z1"]
c = sig["c"]
cinv = inverse(sig["c"])
s1 = mul(poly_sub(z1, y1), cinv)
s1 = mul(s1, [1] + 511*[0])
print(s1)
assert all(x in (Q-1, 0, 1) for x in s1)
s2 = poly_sub(t, mul(mul(a, s1), 510*[0]+[-1,0]))
assert all(x in (Q-1, 0, 1) for x in s2)
# Decrypt
from Cryptodome.Hash import SHA256
from Cryptodome.Cipher import AES
key_s = str(s1).encode() + str(s2).encode()
print(key_s)
key = SHA256.new(key_s).digest()
E = AES.new(key, AES.MODE_CBC, iv=bytes.fromhex(crypt["iv"]))
secret = E.decrypt(bytes.fromhex(crypt["enc"]))
print(secret)
Données
Clé publique pub
{"a": [1632237, 5378119, 5195535, 5821714, 2733325, 462783, 4436908, 5058867, 7275176, 4233964, 3439651, 6237734, 1472907, 1238717, 7846666, 44505, 5139083, 1874581, 6131283, 6402909, 6377030, 5057966, 4036945, 7889866, 3787711, 748844, 3304758, 5302285, 5155563, 5527297, 4836489, 2468371, 2619147, 1798286, 2545565, 6085668, 2870650, 66623, 890396, 2233623, 7205725, 6317262, 3976219, 7500130, 3053945, 1520362, 7464284, 5918375, 1808708, 5595186, 1100208, 8375644, 1370911, 554311, 402290, 4820092, 2923925, 3143919, 7151477, 5759217, 5930870, 2866920, 2866884, 4501605, 2886561, 7340237, 3240123, 4356646, 5221232, 2373095, 7952327, 5765972, 3553029, 905809, 2197034, 3874155, 5424209, 3667466, 4608004, 2468672, 1571225, 5235772, 1516594, 3274063, 2520173, 2687501, 5759764, 5296527, 8185881, 4084767, 2789371, 8367596, 7332820, 6262960, 4084008, 339119, 63399, 8111210, 4427197, 8220534, 3931708, 7208544, 3477874, 4902070, 3270368, 1902816, 4432254, 7562122, 6649181, 8230106, 5533549, 3185573, 5078036, 523746, 7755905, 1661549, 5378668, 75861, 4529680, 7788082, 575749, 4838166, 7730532, 1357, 687404, 1015185, 4948533, 5552258, 4016812, 5263201, 4210719, 4097350, 411277, 635463, 2251829, 3984067, 2858927, 4827137, 421887, 1781836, 2727514, 343331, 7269073, 3284769, 5692938, 707550, 363892, 2146709, 7489830, 399183, 2059531, 876107, 374901, 5316111, 8309462, 3329801, 5537268, 6670893, 4481949, 5401334, 2087948, 5450132, 3086208, 2462943, 6834256, 5692696, 7957025, 1604661, 8062804, 6794525, 5664405, 3719877, 5025902, 1040302, 1052228, 7736549, 426504, 7470408, 3874343, 3755821, 428731, 6873221, 3157160, 6604232, 4245751, 839128, 4148192, 6686892, 3034889, 1897420, 6043298, 7121440, 4361707, 3172471, 6496615, 538298, 4800998, 1654650, 3937906, 2955303, 2670894, 7300479, 6150540, 7354324, 5587435, 3551551, 3552364, 7053582, 3799344, 2969152, 5554228, 5436279, 8076264, 8103430, 1424713, 7603060, 5013802, 797020, 111540, 5380454, 86567, 94089, 3884145, 8340119, 5645122, 3024172, 3683736, 529626, 1857276, 3681173, 1572109, 6297685, 2512678, 1970537, 4361242, 1075412, 5407768, 4511079, 3323659, 841238, 1276719, 724542, 6243844, 6351013, 3070318, 5444782, 3743216, 3951257, 1355610, 8293601, 800961, 4817479, 7702749, 4700442, 7221447, 3171280, 3654441, 2785337, 8237559, 6618059, 1399338, 2909535, 1709977, 7504651, 6185262, 8103612, 6048225, 5972839, 1326884, 740831, 4401848, 5464684, 7293636, 4961625, 899195, 22956, 3639925, 8065760, 281492, 440218, 3529990, 5045016, 7572531, 6265381, 3285847, 3117142, 1275872, 4324676, 677406, 3483473, 219004, 2150026, 2181726, 5050092, 3495478, 8382074, 7143208, 3761041, 5277379, 1101930, 4737541, 1166709, 3413445, 738773, 6567397, 7296018, 3584228, 6611911, 3040845, 2341273, 38998, 3395143, 1216937, 8358112, 469630, 4086985, 755249, 2178145, 3949627, 4625027, 3030191, 8170770, 6049750, 236031, 2775155, 1784629, 2681879, 3169748, 593923, 7218749, 7173997, 2182480, 8153000, 6303828, 4889400, 2205362, 227754, 7506579, 9827, 1966067, 8154220, 4560118, 1583110, 7513818, 2327404, 4348895, 6626433, 5317050, 1715131, 2553461, 3252410, 8103957, 5437548, 2425914, 669971, 6508535, 400929, 946030, 6652156, 5164807, 8104605, 2193400, 6745292, 6061418, 7093484, 7041299, 7711911, 175093, 8242641, 1536310, 6846334, 4791872, 1695801, 5118441, 7665833, 2428674, 4892647, 6217917, 1324478, 5349448, 6541151, 1728675, 4970981, 75006, 3978764, 2697894, 4951951, 2767419, 7714281, 7350606, 5808932, 91195, 7682000, 3185755, 2478131, 4267230, 8143134, 6779555, 1658464, 2370594, 1378408, 4890554, 4786272, 7837560, 1581634, 2543541, 3723322, 4975703, 5567327, 461377, 8270128, 7028583, 7878791, 4019500, 3487700, 5277340, 6473028, 3783565, 3593186, 303124, 3937992, 328222, 6515219, 6593696, 4130190, 7911365, 1665104, 6164964, 474477, 5974585, 7177642, 2406557, 6269298, 552751, 6886626, 3495558, 507700, 6309923, 145684, 2190216, 5540382, 2168452, 4108881, 1020349, 2052526, 6246580, 6629163, 1025809, 5605161, 4917129, 2634070, 2683729, 2943081, 4662298, 3371563, 7676972, 1519345, 1079031, 2158334, 5560177, 6671786, 5260498, 1695452, 7523147, 1052028, 7657908, 5477550, 2879586, 7759748, 2385049, 6914022, 1675489, 4012581, 5818777, 4208006, 4332813, 5192781, 6612296, 6217761, 1541133, 6117977, 3498260, 4884352, 6096298, 5506697, 1052034, 367338, 7404423, 3748250, 2337506, 7167221, 2026096, 710921, 7078519, 1440002, 8325053, 7561442, 8054609, 6786184, 6203217, 1844904, 3156484, 3836475, 6077104, 178088, 8298017, 5711102, 7409058, 7458476, 5837975, 3632408, 7304636], "t": [3921273, 7249125, 3639712, 1625688, 8013052, 3678408, 6123678, 3097293, 1208171, 2919500, 4046107, 5804904, 8270482, 1491925, 4763287, 1196165, 7323956, 2546602, 6668649, 1017077, 8081211, 4599654, 2536749, 1435935, 4189459, 5144240, 158602, 7551510, 4129366, 4402532, 1220695, 5526901, 2998191, 4754848, 1153336, 7913, 446307, 4180671, 3287682, 149527, 4772465, 3105908, 1659932, 7241053, 3434567, 1791247, 3140783, 6954308, 7701930, 1458232, 4992324, 1134739, 958573, 6897277, 8133657, 3856929, 95318, 7853743, 2418235, 1959730, 2193849, 848573, 7486769, 7532439, 3335503, 5853433, 1847642, 5957301, 8081627, 3997578, 2301130, 2848169, 5774258, 1643997, 6786833, 4470128, 2817426, 5675033, 1593477, 4987204, 1216349, 3696063, 2327877, 1684634, 2218572, 7038151, 4684758, 1919613, 4534248, 535139, 6589476, 7590345, 2382571, 2187184, 2256910, 559818, 633415, 6873316, 574591, 8090299, 5775517, 7877939, 5706955, 2956335, 3079419, 6047802, 2991516, 5379762, 4861530, 6176262, 3328297, 2742168, 2617946, 7922405, 133329, 3185552, 3873817, 5741730, 6627302, 5267203, 3314279, 4096765, 4220610, 2104351, 4336963, 307483, 1398507, 6031169, 3693449, 7104832, 6621379, 2989425, 3443781, 130840, 2837206, 8289657, 1622683, 7273298, 5165639, 266721, 2899657, 2692194, 4971877, 429189, 1994559, 3193606, 3756044, 1839172, 2423966, 948706, 7646848, 4897386, 44015, 3406600, 5038263, 4043476, 3251984, 1545669, 5165324, 1201295, 6512153, 7580655, 6321799, 124464, 237646, 8043971, 3011898, 4540580, 735152, 7775890, 6880735, 2788566, 5799948, 7090535, 5886277, 2603872, 7138665, 5904914, 4118268, 3091934, 5760011, 6632405, 5441806, 290827, 2427964, 1718124, 7855856, 763976, 5699902, 1388603, 7003277, 1483618, 5078860, 4381543, 1755097, 447453, 3550018, 4689473, 5312487, 104635, 6692816, 5827110, 2256728, 2933152, 4959496, 8057506, 2355369, 8012048, 1038778, 4537092, 3673113, 964483, 6535910, 2568925, 6550839, 3724756, 6596067, 3494931, 8097276, 6052989, 8180438, 260591, 7081821, 8055278, 778254, 4981588, 7027235, 5893352, 6996175, 5779483, 6957387, 6993707, 7599533, 6162627, 427824, 2145567, 1680904, 384335, 3681211, 7923038, 2991354, 7427941, 4358119, 3326451, 8281363, 5826069, 3692293, 5310237, 2063800, 6165683, 7056999, 8028631, 7615947, 7595856, 5970316, 8065667, 7725318, 3025828, 7015136, 5875901, 2859626, 388193, 5626252, 5946443, 7471676, 6415077, 5367015, 4088078, 5893437, 7302444, 3704510, 8116128, 2584378, 309249, 7593638, 156695, 5427423, 2137100, 5155305, 1991513, 6714267, 3055917, 3550254, 1109101, 6145489, 3692644, 247241, 5039124, 7631518, 6336971, 2681972, 2742651, 1248965, 3927895, 4552747, 8008486, 4771494, 4321813, 7926473, 5285903, 7587903, 7073695, 2681404, 7431471, 5419092, 2196736, 4446197, 2340540, 6862323, 5486011, 3404023, 2002253, 2343321, 4107058, 5635964, 7356131, 7399430, 762596, 4752857, 1889411, 8272743, 4224423, 7147865, 3399194, 5221063, 5725672, 4661115, 5031657, 1545325, 2489707, 3372585, 1990208, 5867905, 7295421, 8164613, 6916383, 5265188, 7885449, 4230346, 4436618, 2406478, 3648072, 590223, 4313026, 2852129, 276904, 3934056, 2394060, 7592876, 5213923, 6419991, 3206597, 4425584, 2423710, 4236621, 5269537, 1721393, 5791592, 2342068, 4315038, 4190548, 845672, 6506596, 2883864, 2433650, 1525990, 4823957, 1108286, 7859947, 751915, 6795544, 2913778, 7925906, 1588599, 1074221, 1286204, 1524914, 6104056, 3982070, 3230182, 4353550, 4565421, 2797276, 8153005, 374040, 5699828, 4440510, 1702090, 7510096, 5578885, 284628, 1233401, 2493145, 8013406, 387040, 5235523, 2691562, 4337164, 6003640, 4844349, 6386112, 226216, 1024644, 8345985, 6265963, 73220, 2065248, 7588719, 1797625, 7958544, 2908933, 6398832, 126477, 5883779, 5676302, 7580387, 1911760, 4699091, 7516449, 3794513, 2739615, 6957152, 454958, 4372628, 6225201, 5433975, 472709, 2889126, 3727796, 7579093, 6652199, 4318127, 7500600, 4076269, 1434027, 4012927, 4330870, 7437830, 1932635, 491987, 6158738, 5015388, 7172556, 4361035, 5459913, 4841162, 5423369, 2040758, 2251160, 7718354, 1480973, 2202262, 7811646, 2273018, 2067831, 7126410, 6852940, 2615239, 1376040, 4491119, 6118420, 287377, 5586379, 5291441, 363149, 4458998, 6958173, 4308391, 4925856, 4166462, 3031599, 5521313, 3229813, 6662440, 7320343, 7703125, 1138270, 3711448, 2120821, 1740494, 3550335, 198975, 8058921, 3097183, 5673326, 1968307, 5476482, 366475, 2098476, 414468, 1925513, 5726575, 1150335, 2987599, 1889214, 176959, 806070, 1354987, 5681877, 8038996, 8254931, 6089937, 795680, 4575154, 3552186, 1571159, 4907596, 3433576, 2340555, 3625750, 8116376, 2704116]}
Première signature:
{"message": "LQmgRMudiUzGASyJsWCB", "z1": [15703, 7460, 14701, 1839, 8380788, 8380065, 13283, 8372377, 8374681, 14918, 7895, 8371508, 8378035, 8372342, 8372726, 9176, 6654, 6389, 3605, 1472, 8379336, 4188, 8382433, 8367993, 8382513, 8381679, 8373397, 8375231, 3043, 896, 8371088, 9567, 12769, 8382575, 11397, 8374404, 4030, 8380245, 8376710, 8370849, 10310, 6518, 8373337, 12511, 1784, 8368224, 8378025, 8369668, 2791, 8369156, 1069, 8378377, 6699, 8368735, 2497, 3354, 8373353, 7541, 8378439, 2720, 8375502, 8371402, 8370548, 8382093, 8373702, 8379082, 8692, 8149, 8017, 7071, 8381700, 8378777, 8369705, 8378757, 8380928, 8367806, 5056, 3068, 15026, 6658, 3856, 2699, 8367663, 6285, 8379552, 9715, 8379416, 12791, 8372469, 12065, 8379205, 8369957, 8369299, 8372548, 13385, 6110, 8826, 10113, 8383478, 8369178, 8367767, 8380213, 8380078, 8377779, 8376316, 8368916, 8383470, 8380314, 11683, 8371091, 8370515, 8370001, 12136, 2246, 12085, 15952, 8381807, 8374241, 8377179, 8373282, 8369289, 8370280, 8368601, 3483, 8372668, 3171, 560, 14605, 16050, 8374178, 8380736, 8373705, 8374216, 8382906, 12209, 15291, 8380225, 8369339, 5532, 8377340, 8367432, 8382682, 1823, 8377213, 6434, 8367819, 11973, 12103, 11029, 9514, 8376771, 8372235, 16239, 8377840, 8373328, 8379345, 15792, 8373937, 8372841, 8378621, 8382578, 8372678, 8373720, 8367546, 4744, 8369839, 8374248, 2045, 8371197, 8374644, 8382150, 8375665, 14242, 8382863, 7935, 4870, 11863, 12792, 8374826, 8372643, 8380610, 1958, 8380429, 8372092, 5955, 8371532, 11846, 6947, 9615, 941, 8374023, 8377367, 325, 14156, 13920, 3499, 8381635, 8375449, 4663, 8369198, 12214, 8367825, 8368173, 8371349, 8378787, 8368892, 8380168, 8373733, 8370654, 13843, 8367404, 8381427, 3597, 6067, 8380786, 8373728, 8380290, 8375110, 8367682, 1220, 11436, 8378865, 15420, 14283, 8380231, 8369618, 2415, 8374043, 8370694, 9910, 8372640, 8375487, 8378386, 5178, 16035, 8370683, 13844, 8377598, 10194, 12996, 8380061, 15661, 8371735, 2067, 8373507, 8370958, 8367227, 8373731, 7310, 8368574, 5116, 8371957, 15137, 8381229, 1602, 13123, 8376199, 8379981, 13323, 5894, 951, 8378774, 8376807, 270, 1027, 7377, 8378823, 8374760, 9393, 8375638, 14205, 1542, 7630, 8370642, 2096, 14453, 8377823, 8368151, 12064, 8369912, 8371120, 10989, 8367861, 8380080, 8817, 4849, 8380233, 8618, 9565, 4407, 5845, 556, 14557, 8369366, 11321, 10812, 8371295, 15221, 236, 5199, 8374785, 8381739, 7946, 5819, 7900, 10316, 8369131, 8377950, 10001, 8371115, 8382551, 5797, 1638, 8379585, 8373871, 3461, 12924, 1663, 8372279, 14530, 10425, 8379998, 9602, 8371410, 8038, 8375956, 9180, 2781, 7041, 14473, 15596, 8380366, 8382777, 8374152, 8377285, 10758, 2269, 8372767, 8380573, 1617, 8375469, 8380925, 8370311, 8370339, 961, 13819, 8378835, 8428, 8367366, 8369605, 14438, 8374028, 8378953, 8369031, 8382794, 8374322, 13301, 15512, 9134, 8381935, 4061, 8369034, 8382548, 10757, 6340, 3113, 9564, 12858, 2704, 5121, 8377042, 8374540, 3692, 8373378, 8375348, 14402, 8371061, 14296, 8375072, 2292, 8378474, 8367740, 8374966, 8373650, 14939, 8367905, 2848, 8832, 578, 14243, 9923, 14762, 8375845, 8379870, 12783, 8379576, 8369478, 1580, 15524, 8003, 8378203, 8381268, 11322, 8378477, 6675, 8370812, 3062, 12561, 1003, 5262, 8375477, 2805, 8373383, 8370908, 719, 8379015, 8377887, 1843, 8378671, 8372097, 6838, 8376224, 8375275, 1997, 8373243, 8368285, 8378100, 7291, 8375668, 8639, 13352, 13499, 13610, 11819, 9943, 6193, 12866, 15583, 8377575, 8369888, 8376190, 11368, 8378055, 4214, 8371894, 16348, 1714, 14335, 2658, 4942, 11675, 8375764, 8380660, 8378291, 4634, 8368224, 2867, 8368076, 6228, 8369250, 8379616, 11698, 8372595, 8375025, 8376262, 5837, 8383314, 8368699, 9788, 8378127, 8375530, 9995, 8370789, 8377192, 4118, 6494, 13645, 6317, 8381414, 12499, 8374233, 7843, 14389, 1646, 8381910, 14252, 11287, 8375744, 8380550, 8369699, 12629, 8355, 8367419, 8369388, 8372447, 8373931, 8381658, 8377593, 8378233, 4230, 4604, 7361, 15017, 965, 9967, 8376582, 8207, 8372546, 6358, 8367671, 8376696, 8374031], "z2": [8378515, 999, 8379351, 13485, 9090, 7827, 15498, 8381774, 13546, 8379481, 8378979, 8378575, 6838, 8375962, 8367341, 16355, 2901, 15400, 8373374, 7173, 8375449, 10735, 12915, 8370822, 8373611, 4960, 8369370, 16115, 4910, 8429, 2079, 11475, 5128, 8376049, 15881, 15377, 9416, 3577, 13714, 8382931, 15147, 8370370, 8374001, 8378531, 11691, 8379160, 3186, 8375721, 8372541, 8369220, 15424, 8369572, 8381163, 10919, 6109, 8380993, 8897, 13023, 8380167, 10648, 11271, 8369146, 13566, 10752, 8369922, 13905, 10350, 2148, 8379479, 9097, 8368404, 8376226, 12755, 9307, 10386, 4790, 1767, 8374759, 8376983, 8376390, 14561, 8433, 8376850, 6122, 15857, 8368887, 479, 8375863, 8378668, 8368626, 5646, 8369144, 6282, 286, 7678, 8374185, 15444, 8382907, 8376902, 8210, 7382, 14287, 13452, 8376922, 2854, 2215, 8373342, 1777, 8368384, 7472, 8381384, 8368948, 8371984, 3027, 8367538, 1043, 7170, 15488, 8372301, 9958, 8370265, 2058, 1150, 15989, 1493, 8367242, 11747, 9500, 8370986, 5660, 8372917, 8369402, 6320, 12386, 8374661, 8383276, 7192, 1786, 5607, 8379740, 12845, 8373228, 918, 8378001, 8381976, 8376251, 8379798, 8379909, 13252, 8373438, 8368335, 8374458, 8379611, 9275, 8373076, 4698, 8380441, 8383143, 15325, 8376193, 8367828, 4759, 2992, 8369291, 8020, 8369360, 8382579, 12483, 6225, 1442, 8367750, 3071, 8374250, 8373165, 8376256, 14433, 8381241, 8375516, 8381273, 8378119, 8382751, 8380931, 8380603, 13619, 8370738, 10466, 8376613, 5299, 1651, 8369491, 8368041, 8374509, 16106, 8375559, 8374110, 9486, 8375262, 11850, 11853, 8372785, 8381402, 13663, 8373413, 2490, 2921, 8375480, 8375704, 14699, 8371597, 9505, 9682, 8381765, 12108, 8369316, 13396, 8367199, 8380276, 14086, 8380678, 13745, 8367698, 8370584, 8380435, 8370654, 8369773, 8372425, 8381636, 8377889, 1277, 8377465, 8381084, 3336, 12766, 8379500, 15041, 7309, 8378481, 8367186, 6976, 8084, 5818, 8375761, 8381866, 15399, 8376482, 8382255, 8416, 1522, 8375874, 14784, 8374154, 4048, 3438, 8353, 8381113, 15854, 6267, 8373705, 6007, 9669, 14152, 8378899, 8374605, 1779, 8370590, 8378160, 8379167, 1084, 8372836, 8368728, 904, 8375412, 8381282, 12460, 8376355, 8372555, 8371882, 7762, 8377795, 2852, 8376802, 13002, 8373075, 8376768, 8379476, 8378796, 1839, 8381640, 3179, 8377660, 8382794, 14127, 8272, 3639, 4645, 8369311, 7282, 3444, 11836, 9613, 12118, 7719, 8378841, 8383459, 8378197, 12031, 8374458, 8368142, 10611, 8379933, 4763, 8368820, 8377709, 956, 8894, 5010, 8379129, 5123, 497, 649, 898, 2540, 11414, 7812, 8373227, 8381484, 10952, 13349, 3771, 8372886, 8832, 8368028, 7017, 8369573, 8371155, 8370803, 5145, 8369627, 8374538, 8379899, 8367661, 8376333, 1775, 10458, 8380888, 2745, 8370607, 564, 12117, 8368941, 8368038, 8372955, 15153, 14583, 8377182, 8376055, 8380509, 7949, 3099, 8374970, 12982, 5121, 8382233, 8375533, 2728, 8376115, 14716, 9783, 8368567, 6766, 5442, 8369401, 5290, 13330, 8372411, 8380768, 317, 11478, 8373808, 6071, 5795, 8374109, 821, 8372903, 13802, 3434, 8375457, 8795, 8371128, 12842, 8163, 515, 9192, 8374810, 7932, 8378343, 4931, 2860, 9336, 14144, 9095, 12662, 5819, 8376632, 8372798, 8368681, 3214, 8376286, 9945, 1479, 8382258, 8377700, 8381865, 8380485, 8380821, 8368701, 2087, 8376305, 2450, 7317, 5102, 15579, 10914, 3635, 13452, 362, 10005, 8373646, 13270, 14615, 8373934, 13457, 8313, 9563, 8381003, 10531, 889, 5218, 11112, 107, 8368850, 3643, 8372768, 8374187, 8368363, 7009, 8369799, 8369618, 8379131, 11305, 6812, 8373616, 14470, 8383260, 8380063, 8377847, 12239, 12556, 14727, 8373847, 7922, 8382385, 16071, 8368981, 8381136, 259, 1681, 8370192, 8379034, 8381506, 8382869, 13866, 8381869, 13428, 8376807, 13156, 9599, 6276, 8382021, 1079, 11871, 9783, 8372879, 1883, 2789, 7886, 4125, 8367740, 8376563, 8676, 2735, 1207, 10148, 9970, 8377152, 8369459, 8373949, 15323, 10689, 8379971, 8373759, 8372234, 8382839, 4563, 6393, 8380416, 8377929, 14909, 8379244, 862, 8377917, 8375870], "c": [0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0], "y1": [15700, 7467, 14711, 1854, 8380801, 8380058, 13294, 8372401, 8374687, 14921, 7913, 8371501, 8378034, 8372354, 8372737, 9173, 6671, 6402, 3595, 1474, 8379353, 4192, 8382429, 8367991, 8382513, 8381693, 8373425, 8375217, 3058, 893, 8371097, 9582, 12791, 8382575, 11401, 8374427, 4031, 8380247, 8376704, 8370850, 10316, 6535, 8373328, 12508, 1791, 8368235, 8378020, 8369666, 2801, 8369186, 1091, 8378369, 6696, 8368728, 2502, 3353, 8373354, 7527, 8378440, 2724, 8375500, 8371409, 8370532, 8382084, 8373700, 8379078, 8694, 8150, 8029, 7077, 8381695, 8378783, 8369707, 8378753, 8380922, 8367807, 5057, 3079, 15023, 6657, 3838, 2684, 8367660, 6296, 8379545, 9726, 8379411, 12775, 8372456, 12072, 8379189, 8369949, 8369299, 8372544, 13386, 6114, 8838, 10101, 8383468, 8369185, 8367764, 8380198, 8380071, 8377771, 8376320, 8368901, 8383475, 8380321, 11689, 8371098, 8370506, 8370020, 12135, 2236, 12091, 15919, 8381795, 8374253, 8377165, 8373287, 8369298, 8370277, 8368596, 3483, 8372652, 3159, 556, 14612, 16048, 8374173, 8380731, 8373693, 8374208, 8382886, 12196, 15280, 8380215, 8369322, 5527, 8377337, 8367418, 8382671, 1817, 8377200, 6442, 8367814, 11961, 12100, 11023, 9518, 8376759, 8372222, 16221, 8377828, 8373328, 8379331, 15787, 8373915, 8372831, 8378626, 8382554, 8372672, 8373712, 8367534, 4736, 8369829, 8374221, 2031, 8371200, 8374612, 8382144, 8375667, 14236, 8382842, 7931, 4855, 11858, 12795, 8374830, 8372607, 8380601, 1943, 8380430, 8372085, 5958, 8371510, 11852, 6933, 9613, 950, 8374008, 8377357, 332, 14143, 13907, 3502, 8381635, 8375457, 4659, 8369192, 12215, 8367829, 8368166, 8371335, 8378790, 8368897, 8380165, 8373712, 8370649, 13832, 8367406, 8381426, 3597, 6064, 8380784, 8373731, 8380276, 8375109, 8367681, 1218, 11431, 8378858, 15423, 14274, 8380236, 8369613, 2422, 8374044, 8370680, 9907, 8372656, 8375490, 8378378, 5190, 16044, 8370670, 13854, 8377604, 10181, 13002, 8380064, 15665, 8371731, 2062, 8373507, 8370959, 8367225, 8373744, 7330, 8368579, 5127, 8371965, 15153, 8381252, 1601, 13138, 8376214, 8379993, 13327, 5910, 968, 8378774, 8376820, 285, 1050, 7402, 8378836, 8374768, 9391, 8375670, 14211, 1555, 7636, 8370657, 2118, 14485, 8377836, 8368169, 12072, 8369923, 8371124, 11023, 8367863, 8380103, 8826, 4868, 8380241, 8633, 9571, 4429, 5860, 586, 14581, 8369384, 11330, 10833, 8371309, 15240, 268, 5204, 8374808, 8381766, 7955, 5843, 7926, 10344, 8369153, 8377973, 10025, 8371151, 8382561, 5813, 1663, 8379596, 8373881, 3488, 12957, 1681, 8372282, 14561, 10421, 8380009, 9613, 8371422, 8059, 8375994, 9201, 2799, 7052, 14497, 15617, 8380385, 8382787, 8374163, 8377312, 10761, 2282, 8372772, 8380592, 1626, 8375489, 8380956, 8370331, 8370359, 986, 13843, 8378837, 8449, 8367384, 8369615, 14463, 8374045, 8378971, 8369042, 8382803, 8374338, 13313, 15524, 9137, 8381952, 4076, 8369046, 8382554, 10763, 6353, 3095, 9595, 12895, 2724, 5130, 8377069, 8374546, 3703, 8373379, 8375353, 14409, 8371077, 14304, 8375096, 2307, 8378498, 8367747, 8374967, 8373654, 14960, 8367938, 2860, 8828, 581, 14262, 9944, 14777, 8375849, 8379878, 12805, 8379584, 8369490, 1601, 15533, 8005, 8378221, 8381278, 11346, 8378485, 6694, 8370824, 3066, 12573, 1019, 5285, 8375479, 2815, 8373405, 8370932, 736, 8379019, 8377893, 1862, 8378691, 8372106, 6866, 8376212, 8375274, 2020, 8373247, 8368287, 8378108, 7305, 8375687, 8648, 13378, 13509, 13617, 11824, 9939, 6207, 12874, 15592, 8377593, 8369906, 8376193, 11371, 8378075, 4217, 8371903, 16373, 1721, 14345, 2669, 4960, 11683, 8375757, 8380676, 8378299, 4634, 8368229, 2863, 8368075, 6233, 8369251, 8379616, 11721, 8372612, 8375030, 8376258, 5835, 8383315, 8368698, 9774, 8378104, 8375540, 10005, 8370798, 8377208, 4091, 6483, 13638, 6314, 8381429, 12512, 8374240, 7846, 14407, 1660, 8381913, 14253, 11276, 8375755, 8380555, 8369727, 12633, 8353, 8367414, 8369382, 8372465, 8373942, 8381659, 8377587, 8378219, 4239, 4614, 7361, 14999, 959, 9952, 8376583, 8211, 8372544, 6353, 8367659, 8376672, 8374039]}
Secret chiffré:
{"iv": "21171db2bbe684a8afb6c9f81b43c634", "enc": "d258ee201e92ddaaac0dc435639986dd8e1e1f44927bef6e10d9da365aefc6524727bd5e5df11010e9d23d97cd839cb3941c38584c796c6037edc4f4f418e3ab11bbee787b4a7117457704f67ae127da"}
Post-scriptum
Le système NTRU vu dans Millenium utilise également des polynômes à petits coefficients modulo X^(2^N)+1, modulo un nombre premier.