原理等来自相关链接：NTRU-密码学 |NTRU算法 |wiki-NTRUEncrypt
简介 算法流程如下：
初始化生成和公钥 初始化(N, p , q, d)
N：次数参数，为正整数。经典取值为素数n=251。
q：大模数，为正整数。经典取值为2的幂q=256。
p：小模数，为小的奇素数或多项式。经典取值为素数p=3。
d：用来限制非0系数的个数，为整数。当n=251时，d=72。
NTRU原始方案的一个说明： 中心化处理，即模q运算或模p运算的结果以0为中心。比如模3运算的结果属于{-1，0，1}而不是{0，1，2}，模256运算的结果属于{-127，-126，…，128}而不是{0，1…，255}。这样的中心化处理在代数上没有任何不同，但使得尺寸变小了。环
此篇不做。
生成公钥：
生成两个次数为N - 1的多项式、
例，N = 10, p = 3, q = 512, d = 3时(N, p, q, d) = (10, 3, 512, 3):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 R.<x> = ZZ[] def T(d1, d2): assert N >= d1+d2 s = [1]*d1 + [-1]*d2 + [0]*(N-d1-d2) shuffle(s) return R(s) f = T(d+1, d) g = T(d, d) print("f = ", f) # f = x^7 + x^6 + x^5 + x^4 - x^2 - x - 1 print("g = ", g) # g = -x^9 + x^5 + x^4 - x^2 - x + 1
公钥h满足：
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 def polyMod(f, q): g = [f[i]%q for i in range(N)] return R(g) def liftMod(f, q): g = list(((f[i] + q//2) % q) - q//2 for i in range(N)) return R(g) def invertModPrime(f, p): Rp = R.change_ring(Integers(p)).quotient(x^N-1) return R(lift(1 / Rp(f))) def invertModPow2(f, q): assert q.is_power_of(2) g = invertModPrime(f,2) while True: r = liftMod(convolution(g,f),q) if r == 1: return g g = liftMod(convolution(g,2 - r),q) def convolution(f, g): return (f*g) % (x^N-1) Fp = polyMod(invertModPrime(f, p), p) Fq = polyMod(invertModPow2(f, q), q) h = polyMod(convolution(Fq, g), q) print("Fp = ", Fp) # Fp = 2*x^9 + 2*x^8 + 2*x^6 + 2*x^5 + x^4 + x^3 + 2*x + 1 print("Fq = ", Fq) # Fq = 419*x^9 + 465*x^8 + 233*x^7 + 373*x^6 + 186*x^5 + 93*x^4 + 47*x^3 + 279*x^2 + 140*x + 326 print("h = ", h) # h = 186*x^9 + 92*x^8 + 47*x^7 + 280*x^6 + 139*x^5 + 326*x^4 + 419*x^3 + 464*x^2 + 234*x + 373 # 并不是所有的f，g都可以生成h。因为f很可能在上述模下没有逆。所以最好这两段代码应该用try封装，并封入genKey()的函数。
至此，公钥h 产生。私钥为
Encryption
加密方式为：
1 2 3 def encrypt(m, h): e = liftMod(p*convolution(h, T(d, d)) + m, q) return e
Decryption
Dasctf 2022 July — esayNTRU 题目 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 from Crypto.Hash import SHA3_256 from Crypto.Cipher import AES from Crypto.Util.Padding import pad from secret import flag # parameters N = 10 p = 3 q = 512 d = 3 assert q>(6*d+1)*p R.<x> = ZZ[] #d1 1s and #d2 -1s def T(d1, d2): assert N >= d1+d2 s = [1]*d1 + [-1]*d2 + [0]*(N-d1-d2) shuffle(s) return R(s) def invertModPrime(f, p): Rp = R.change_ring(Integers(p)).quotient(x^N-1) return R(lift(1 / Rp(f))) def convolution(f, g): return (f*g) % (x^N-1) def liftMod(f, q): g = list(((f[i] + q//2) % q) - q//2 for i in range(N)) return R(g) def polyMod(f, q): g = [f[i]%q for i in range(N)] return R(g) def invertModPow2(f, q): assert q.is_power_of(2) g = invertModPrime(f,2) while True: r = liftMod(convolution(g,f),q) if r == 1: return g g = liftMod(convolution(g,2 - r),q) def genMessage(): result = list(randrange(p) - 1 for j in range(N)) return R(result) def genKey(): while True: try: f = T(d+1, d) g = T(d, d) Fp = polyMod(invertModPrime(f, p), p) Fq = polyMod(invertModPow2(f, q), q) break except: continue h = polyMod(convolution(Fq, g), q) return h, (f, g) def encrypt(m, h): e = liftMod(p*convolution(h, T(d, d)) + m, q) return e # Step 1 h, secret = genKey() m = genMessage() e = encrypt(m, h) print('h = %s' % h) print('e = %s' % e) # Step 2 sha3 = SHA3_256.new() sha3.update(bytes(str(m).encode('utf-8'))) key = sha3.digest() cypher = AES.new(key, AES.MODE_ECB) c = cypher.encrypt(pad(flag, 32)) print('c = %s' % c) h = 39*x^9 + 60*x^8 + 349*x^7 + 268*x^6 + 144*x^5 + 469*x^4 + 449*x^3 + 165*x^2 + 248*x + 369 e = -144*x^9 - 200*x^8 - 8*x^7 + 248*x^6 + 85*x^5 + 102*x^4 + 167*x^3 + 30*x^2 - 203*x - 78 c = b'\xb9W\x8c\x8b\x0cG\xde\x7fl\xf7\x03\xbb9m\x0c\xc4L\xfe\xe9Q\xad\xfd\xda!\x1a\xea@}U\x9ay4\x8a\xe3y\xdf\xd5BV\xa7\x06\xf9\x08\x96="f\xc1\x1b\xd7\xdb\xc1j\x82F\x0b\x16\x06\xbcJMB\xc8\x80'
解题思路 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #sage from Crypto.Hash import SHA3_256 from Crypto.Cipher import AES c = b'\xb9W\x8c\x8b\x0cG\xde\x7fl\xf7\x03\xbb9m\x0c\xc4L\xfe\xe9Q\xad\xfd\xda!\x1a\xea@}U\x9ay4\x8a\xe3y\xdf\xd5BV\xa7\x06\xf9\x08\x96="f\xc1\x1b\xd7\xdb\xc1j\x82F\x0b\x16\x06\xbcJMB\xc8\x80' R.<x> = ZZ[] import itertools t = [1, 0, -1] for i in itertools.product(t,repeat=10): m = list(i) m = R(m) sha3 = SHA3_256.new() sha3 = sha3.update(bytes(str(m).encode('utf-8'))) key = sha3.digest() cypher = AES.new(key, AES.MODE_ECB) m = cypher.decrypt(c) if b'DASCTF' in m: print(m)
1 2 3 4 #sage Integers(q)(1/3) # output: 171 h3 = (171*h)%q
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 #sage import random from Crypto.Util.number import * Zx.<x> = ZZ[] # R.<x> = ZZ[] def balancedmod(f,q): g = list( ((f[i] + q//2) % q) - q//2 for i in range(n) ) return Zx(g) def cyclicconvolution(f, g): return (f*g) % (x^n-1) def invertmodprime(f,p): T = Zx.change_ring(Integers(p)).quotient(x^n-1) return Zx(lift(1 / T(f))) def invertmodpowerof2(f,q): assert q.is_power_of(2) g = invertmodprime(f,2) while True: r = balancedmod(cyclicconvolution(g,f),q) if r == 1: return g g = balancedmod(cyclicconvolution(g,2 - r),q) def encrypt(message, publickey): r = rpoly() return balancedmod(cyclicconvolution(publickey, r) + message, q) def decrypt(cipher,f,fp): # cipher=Zx(cipher) a=balancedmod(cyclicconvolution(f, cipher), q) m=balancedmod(cyclicconvolution(fp, a),p) return m def attack(publickey): recip3 = lift(1/Integers(q)(3)) publickeyover3 = balancedmod(recip3 * publickey,q) M = matrix(2 * n) for i in range(n): M[i,i] = q for i in range(n): M[i+n,i+n] = 1 c = cyclicconvolution(x^i,publickeyover3) for j in range(n): M[i+n,j] = c[j] M = M.LLL() for j in range(2 * n): try: f = Zx(list(M[j][n:])) f3 = invertmodprime(f,3) return (f,f3) except:pass return (f,f) n = 10 p = 3 q = 512 d = 3 assert q>(6*d+1)*p h = 39*x^9 + 60*x^8 + 349*x^7 + 268*x^6 + 144*x^5 + 469*x^4 + 449*x^3 + 165*x^2 + 248*x + 369 e = -144*x^9 - 200*x^8 - 8*x^7 + 248*x^6 + 85*x^5 + 102*x^4 + 167*x^3 + 30*x^2 - 203*x - 78 c = b'\xb9W\x8c\x8b\x0cG\xde\x7fl\xf7\x03\xbb9m\x0c\xc4L\xfe\xe9Q\xad\xfd\xda!\x1a\xea@}U\x9ay4\x8a\xe3y\xdf\xd5BV\xa7\x06\xf9\x08\x96="f\xc1\x1b\xd7\xdb\xc1j\x82F\x0b\x16\x06\xbcJMB\xc8\x80' # publickey,secretkey = keypair() donald = attack(h.coefficients(sparse=False)) m = decrypt(e,donald[0],donald[1]) from Crypto.Hash import SHA3_256 from Crypto.Cipher import AES sha3 = SHA3_256.new() sha3.update(bytes(str(Zx(m)).encode('utf-8'))) key = sha3.digest() cipher = AES.new(key, AES.MODE_ECB) flag = cipher.decrypt(c) print('c = %s' % flag)
NTRUrsa 题目 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 from Crypto.Util.number import * from gmpy2 import * from secret import flag def gen(): p1 = getPrime(256) while True: f = getRandomRange(1, iroot(p1 // 2, 2)[0]) g = getRandomRange(iroot(p1 // 4, 2)[0], iroot(p1 // 2, 2)[0]) if gcd(f, p1) == 1 and gcd(f, g) == 1 and isPrime(g) == 1: break rand = getRandomRange(0, 2 ^ 20) g1 = g ^^ rand h = (inverse(f, p1) * g1) % p1 return h, p1, g, f, g1 def gen_irreducable_poly(deg): while True: out = R.random_element(degree=deg) if out.is_irreducible(): return out h, p1, g, f, g1 = gen() q = getPrime(1024) n = g * q e = 0x10001 c1 = pow(bytes_to_long(flag), e, n) hint = list(str(h)) length = len(hint) bits = 16 p2 = random_prime(2 ^ bits - 1, False, 2 ^ (bits - 1)) R.<x> = PolynomialRing(GF(p2)) P = gen_irreducable_poly(ZZ.random_element(length, 2 * length)) Q = gen_irreducable_poly(ZZ.random_element(length, 2 * length)) N = P * Q S.<x> = R.quotient(N) m = S(hint) c2 = m ^ e print("p1 =", p1) print("c1 =", c1) print("p2 =", p2) print("c2 =", c2) print("n =", n) print("N =", N) ''' p1 = 106472061241112922861460644342336453303928202010237284715354717630502168520267 c1 = 20920247107738496784071050239422540936224577122721266141057957551603705972966457203177812404896852110975768315464852962210648535130235298413611598658659777108920014929632531307409885868941842921815735008981335582297975794108016151210394446009890312043259167806981442425505200141283138318269058818777636637375101005540308736021976559495266332357714 p2 = 64621 c2 = 19921*x^174 + 49192*x^173 + 18894*x^172 + 61121*x^171 + 50271*x^170 + 11860*x^169 + 53128*x^168 + 38658*x^167 + 14191*x^166 + 9671*x^165 + 40879*x^164 + 15187*x^163 + 33523*x^162 + 62270*x^161 + 64211*x^160 + 54518*x^159 + 50446*x^158 + 2597*x^157 + 32216*x^156 + 10500*x^155 + 63276*x^154 + 27916*x^153 + 55316*x^152 + 30898*x^151 + 43706*x^150 + 5734*x^149 + 35616*x^148 + 14288*x^147 + 18282*x^146 + 22788*x^145 + 48188*x^144 + 34176*x^143 + 55952*x^142 + 9578*x^141 + 9177*x^140 + 22083*x^139 + 14586*x^138 + 9748*x^137 + 21118*x^136 + 155*x^135 + 64224*x^134 + 18193*x^133 + 33732*x^132 + 38135*x^131 + 51992*x^130 + 8203*x^129 + 8538*x^128 + 55203*x^127 + 5003*x^126 + 2009*x^125 + 45023*x^124 + 12311*x^123 + 21428*x^122 + 24110*x^121 + 43537*x^120 + 21885*x^119 + 50212*x^118 + 40445*x^117 + 17768*x^116 + 46616*x^115 + 4771*x^114 + 20903*x^113 + 47764*x^112 + 13056*x^111 + 50837*x^110 + 22313*x^109 + 39698*x^108 + 60377*x^107 + 59357*x^106 + 24051*x^105 + 5888*x^104 + 29414*x^103 + 31726*x^102 + 4906*x^101 + 23968*x^100 + 52360*x^99 + 58063*x^98 + 706*x^97 + 31420*x^96 + 62468*x^95 + 18557*x^94 + 1498*x^93 + 17590*x^92 + 62990*x^91 + 27200*x^90 + 7052*x^89 + 39117*x^88 + 46944*x^87 + 45535*x^86 + 28092*x^85 + 1981*x^84 + 4377*x^83 + 34419*x^82 + 33754*x^81 + 2640*x^80 + 44427*x^79 + 32179*x^78 + 57721*x^77 + 9444*x^76 + 49374*x^75 + 21288*x^74 + 44098*x^73 + 57744*x^72 + 63457*x^71 + 43300*x^70 + 1508*x^69 + 13775*x^68 + 23197*x^67 + 43070*x^66 + 20751*x^65 + 47479*x^64 + 18496*x^63 + 53392*x^62 + 10387*x^61 + 2317*x^60 + 57492*x^59 + 25441*x^58 + 52532*x^57 + 27150*x^56 + 33788*x^55 + 43371*x^54 + 30972*x^53 + 39583*x^52 + 36407*x^51 + 35564*x^50 + 44564*x^49 + 1505*x^48 + 47519*x^47 + 38695*x^46 + 43107*x^45 + 1676*x^44 + 42057*x^43 + 49879*x^42 + 29083*x^41 + 42241*x^40 + 8853*x^39 + 33546*x^38 + 48954*x^37 + 30352*x^36 + 62020*x^35 + 39864*x^34 + 9519*x^33 + 24828*x^32 + 34696*x^31 + 2387*x^30 + 27413*x^29 + 55829*x^28 + 40217*x^27 + 30205*x^26 + 42328*x^25 + 6210*x^24 + 52442*x^23 + 58495*x^22 + 2014*x^21 + 26452*x^20 + 33547*x^19 + 19840*x^18 + 5995*x^17 + 16850*x^16 + 37855*x^15 + 7221*x^14 + 32200*x^13 + 8121*x^12 + 23767*x^11 + 46563*x^10 + 51673*x^9 + 19372*x^8 + 4157*x^7 + 48421*x^6 + 41096*x^5 + 45735*x^4 + 53022*x^3 + 35475*x^2 + 47521*x + 27544 n = 31398174203566229210665534094126601315683074641013205440476552584312112883638278390105806127975406224783128340041129316782549009811196493319665336016690985557862367551545487842904828051293613836275987595871004601968935866634955528775536847402581734910742403788941725304146192149165731194199024154454952157531068881114411265538547462017207361362857 N = 25081*x^175 + 8744*x^174 + 9823*x^173 + 9037*x^172 + 6343*x^171 + 42205*x^170 + 28573*x^169 + 55714*x^168 + 17287*x^167 + 11229*x^166 + 42630*x^165 + 64363*x^164 + 50759*x^163 + 3368*x^162 + 20900*x^161 + 55947*x^160 + 7082*x^159 + 23171*x^158 + 48510*x^157 + 20013*x^156 + 16798*x^155 + 60438*x^154 + 58779*x^153 + 9289*x^152 + 10623*x^151 + 1085*x^150 + 23473*x^149 + 13795*x^148 + 2071*x^147 + 31515*x^146 + 42832*x^145 + 38152*x^144 + 37559*x^143 + 47653*x^142 + 37371*x^141 + 39128*x^140 + 48750*x^139 + 16638*x^138 + 60320*x^137 + 56224*x^136 + 41870*x^135 + 63961*x^134 + 47574*x^133 + 63954*x^132 + 9668*x^131 + 62360*x^130 + 15244*x^129 + 20599*x^128 + 28704*x^127 + 26857*x^126 + 34885*x^125 + 33107*x^124 + 17693*x^123 + 52753*x^122 + 60744*x^121 + 21305*x^120 + 63785*x^119 + 54400*x^118 + 17812*x^117 + 64549*x^116 + 20035*x^115 + 37567*x^114 + 38607*x^113 + 32783*x^112 + 24385*x^111 + 5387*x^110 + 5134*x^109 + 45893*x^108 + 58307*x^107 + 33821*x^106 + 54902*x^105 + 14236*x^104 + 58044*x^103 + 41257*x^102 + 46881*x^101 + 42834*x^100 + 1693*x^99 + 46058*x^98 + 15636*x^97 + 27111*x^96 + 3158*x^95 + 41012*x^94 + 26028*x^93 + 3576*x^92 + 37958*x^91 + 33273*x^90 + 60228*x^89 + 41229*x^88 + 11232*x^87 + 12635*x^86 + 17942*x^85 + 4*x^84 + 25397*x^83 + 63526*x^82 + 54872*x^81 + 40318*x^80 + 37498*x^79 + 52182*x^78 + 48817*x^77 + 10763*x^76 + 46542*x^75 + 36060*x^74 + 49972*x^73 + 63603*x^72 + 46506*x^71 + 44788*x^70 + 44905*x^69 + 46112*x^68 + 5297*x^67 + 26440*x^66 + 28470*x^65 + 15525*x^64 + 11566*x^63 + 15781*x^62 + 36098*x^61 + 44402*x^60 + 55331*x^59 + 61583*x^58 + 16406*x^57 + 59089*x^56 + 53161*x^55 + 43695*x^54 + 49580*x^53 + 62685*x^52 + 31447*x^51 + 26755*x^50 + 14810*x^49 + 3281*x^48 + 27371*x^47 + 53392*x^46 + 2648*x^45 + 10095*x^44 + 25977*x^43 + 22912*x^42 + 41278*x^41 + 33236*x^40 + 57792*x^39 + 7169*x^38 + 29250*x^37 + 16906*x^36 + 4436*x^35 + 2729*x^34 + 29736*x^33 + 19383*x^32 + 11921*x^31 + 26075*x^30 + 54616*x^29 + 739*x^28 + 38509*x^27 + 19118*x^26 + 20062*x^25 + 21280*x^24 + 12594*x^23 + 14974*x^22 + 27795*x^21 + 54107*x^20 + 1890*x^19 + 13410*x^18 + 5381*x^17 + 19500*x^16 + 47481*x^15 + 58488*x^14 + 26433*x^13 + 37803*x^12 + 60232*x^11 + 34772*x^10 + 1505*x^9 + 63760*x^8 + 20890*x^7 + 41533*x^6 + 16130*x^5 + 29769*x^4 + 49142*x^3 + 64184*x^2 + 55443*x + 45925 '''
题解
从一道CTF题初探NTRU格密码
exp : sage-jupyter
1 2 3 R.<x> = PolynomialRing(GF(64621 )) N = R(25081 *x^175 + 8744 *x^174 + 9823 *x^173 + 9037 *x^172 + 6343 *x^171 + 42205 *x^170 + 28573 *x^169 + 55714 *x^168 + 17287 *x^167 + 11229 *x^166 + 42630 *x^165 + 64363 *x^164 + 50759 *x^163 + 3368 *x^162 + 20900 *x^161 + 55947 *x^160 + 7082 *x^159 + 23171 *x^158 + 48510 *x^157 + 20013 *x^156 + 16798 *x^155 + 60438 *x^154 + 58779 *x^153 + 9289 *x^152 + 10623 *x^151 + 1085 *x^150 + 23473 *x^149 + 13795 *x^148 + 2071 *x^147 + 31515 *x^146 + 42832 *x^145 + 38152 *x^144 + 37559 *x^143 + 47653 *x^142 + 37371 *x^141 + 39128 *x^140 + 48750 *x^139 + 16638 *x^138 + 60320 *x^137 + 56224 *x^136 + 41870 *x^135 + 63961 *x^134 + 47574 *x^133 + 63954 *x^132 + 9668 *x^131 + 62360 *x^130 + 15244 *x^129 + 20599 *x^128 + 28704 *x^127 + 26857 *x^126 + 34885 *x^125 + 33107 *x^124 + 17693 *x^123 + 52753 *x^122 + 60744 *x^121 + 21305 *x^120 + 63785 *x^119 + 54400 *x^118 + 17812 *x^117 + 64549 *x^116 + 20035 *x^115 + 37567 *x^114 + 38607 *x^113 + 32783 *x^112 + 24385 *x^111 + 5387 *x^110 + 5134 *x^109 + 45893 *x^108 + 58307 *x^107 + 33821 *x^106 + 54902 *x^105 + 14236 *x^104 + 58044 *x^103 + 41257 *x^102 + 46881 *x^101 + 42834 *x^100 + 1693 *x^99 + 46058 *x^98 + 15636 *x^97 + 27111 *x^96 + 3158 *x^95 + 41012 *x^94 + 26028 *x^93 + 3576 *x^92 + 37958 *x^91 + 33273 *x^90 + 60228 *x^89 + 41229 *x^88 + 11232 *x^87 + 12635 *x^86 + 17942 *x^85 + 4 *x^84 + 25397 *x^83 + 63526 *x^82 + 54872 *x^81 + 40318 *x^80 + 37498 *x^79 + 52182 *x^78 + 48817 *x^77 + 10763 *x^76 + 46542 *x^75 + 36060 *x^74 + 49972 *x^73 + 63603 *x^72 + 46506 *x^71 + 44788 *x^70 + 44905 *x^69 + 46112 *x^68 + 5297 *x^67 + 26440 *x^66 + 28470 *x^65 + 15525 *x^64 + 11566 *x^63 + 15781 *x^62 + 36098 *x^61 + 44402 *x^60 + 55331 *x^59 + 61583 *x^58 + 16406 *x^57 + 59089 *x^56 + 53161 *x^55 + 43695 *x^54 + 49580 *x^53 + 62685 *x^52 + 31447 *x^51 + 26755 *x^50 + 14810 *x^49 + 3281 *x^48 + 27371 *x^47 + 53392 *x^46 + 2648 *x^45 + 10095 *x^44 + 25977 *x^43 + 22912 *x^42 + 41278 *x^41 + 33236 *x^40 + 57792 *x^39 + 7169 *x^38 + 29250 *x^37 + 16906 *x^36 + 4436 *x^35 + 2729 *x^34 + 29736 *x^33 + 19383 *x^32 + 11921 *x^31 + 26075 *x^30 + 54616 *x^29 + 739 *x^28 + 38509 *x^27 + 19118 *x^26 + 20062 *x^25 + 21280 *x^24 + 12594 *x^23 + 14974 *x^22 + 27795 *x^21 + 54107 *x^20 + 1890 *x^19 + 13410 *x^18 + 5381 *x^17 + 19500 *x^16 + 47481 *x^15 + 58488 *x^14 + 26433 *x^13 + 37803 *x^12 + 60232 *x^11 + 34772 *x^10 + 1505 *x^9 + 63760 *x^8 + 20890 *x^7 + 41533 *x^6 + 16130 *x^5 + 29769 *x^4 + 49142 *x^3 + 64184 *x^2 + 55443 *x + 45925 ) c2 = R(19921 *x^174 + 49192 *x^173 + 18894 *x^172 + 61121 *x^171 + 50271 *x^170 + 11860 *x^169 + 53128 *x^168 + 38658 *x^167 + 14191 *x^166 + 9671 *x^165 + 40879 *x^164 + 15187 *x^163 + 33523 *x^162 + 62270 *x^161 + 64211 *x^160 + 54518 *x^159 + 50446 *x^158 + 2597 *x^157 + 32216 *x^156 + 10500 *x^155 + 63276 *x^154 + 27916 *x^153 + 55316 *x^152 + 30898 *x^151 + 43706 *x^150 + 5734 *x^149 + 35616 *x^148 + 14288 *x^147 + 18282 *x^146 + 22788 *x^145 + 48188 *x^144 + 34176 *x^143 + 55952 *x^142 + 9578 *x^141 + 9177 *x^140 + 22083 *x^139 + 14586 *x^138 + 9748 *x^137 + 21118 *x^136 + 155 *x^135 + 64224 *x^134 + 18193 *x^133 + 33732 *x^132 + 38135 *x^131 + 51992 *x^130 + 8203 *x^129 + 8538 *x^128 + 55203 *x^127 + 5003 *x^126 + 2009 *x^125 + 45023 *x^124 + 12311 *x^123 + 21428 *x^122 + 24110 *x^121 + 43537 *x^120 + 21885 *x^119 + 50212 *x^118 + 40445 *x^117 + 17768 *x^116 + 46616 *x^115 + 4771 *x^114 + 20903 *x^113 + 47764 *x^112 + 13056 *x^111 + 50837 *x^110 + 22313 *x^109 + 39698 *x^108 + 60377 *x^107 + 59357 *x^106 + 24051 *x^105 + 5888 *x^104 + 29414 *x^103 + 31726 *x^102 + 4906 *x^101 + 23968 *x^100 + 52360 *x^99 + 58063 *x^98 + 706 *x^97 + 31420 *x^96 + 62468 *x^95 + 18557 *x^94 + 1498 *x^93 + 17590 *x^92 + 62990 *x^91 + 27200 *x^90 + 7052 *x^89 + 39117 *x^88 + 46944 *x^87 + 45535 *x^86 + 28092 *x^85 + 1981 *x^84 + 4377 *x^83 + 34419 *x^82 + 33754 *x^81 + 2640 *x^80 + 44427 *x^79 + 32179 *x^78 + 57721 *x^77 + 9444 *x^76 + 49374 *x^75 + 21288 *x^74 + 44098 *x^73 + 57744 *x^72 + 63457 *x^71 + 43300 *x^70 + 1508 *x^69 + 13775 *x^68 + 23197 *x^67 + 43070 *x^66 + 20751 *x^65 + 47479 *x^64 + 18496 *x^63 + 53392 *x^62 + 10387 *x^61 + 2317 *x^60 + 57492 *x^59 + 25441 *x^58 + 52532 *x^57 + 27150 *x^56 + 33788 *x^55 + 43371 *x^54 + 30972 *x^53 + 39583 *x^52 + 36407 *x^51 + 35564 *x^50 + 44564 *x^49 + 1505 *x^48 + 47519 *x^47 + 38695 *x^46 + 43107 *x^45 + 1676 *x^44 + 42057 *x^43 + 49879 *x^42 + 29083 *x^41 + 42241 *x^40 + 8853 *x^39 + 33546 *x^38 + 48954 *x^37 + 30352 *x^36 + 62020 *x^35 + 39864 *x^34 + 9519 *x^33 + 24828 *x^32 + 34696 *x^31 + 2387 *x^30 + 27413 *x^29 + 55829 *x^28 + 40217 *x^27 + 30205 *x^26 + 42328 *x^25 + 6210 *x^24 + 52442 *x^23 + 58495 *x^22 + 2014 *x^21 + 26452 *x^20 + 33547 *x^19 + 19840 *x^18 + 5995 *x^17 + 16850 *x^16 + 37855 *x^15 + 7221 *x^14 + 32200 *x^13 + 8121 *x^12 + 23767 *x^11 + 46563 *x^10 + 51673 *x^9 + 19372 *x^8 + 4157 *x^7 + 48421 *x^6 + 41096 *x^5 + 45735 *x^4 + 53022 *x^3 + 35475 *x^2 + 47521 *x + 27544 )
1 2 3 4 e = 0x10001 phi = (64621 ^ 97 - 1 ) * (64621 ^ 78 - 1 ) d = inverse_mod(e, phi)
1 2 3 m = pow (c2, d, N) print (m)
1 2 3 4 5 6 7 8 9 10 h = 88520242910362871448352317137540300262448941340486475602003226117035863930302 p1 = 106472061241112922861460644342336453303928202010237284715354717630502168520267 v1 = vector(ZZ, [1 , h]) v2 = vector(ZZ, [0 , p1]) m = matrix([v1,v2]) shortest_vector = m.LLL()[0 ] f, g = shortest_vector print (f, g)
1 2 3 4 5 6 7 8 9 from Crypto.Util.number import *g1 = 228679177303871981036829786447405151037 n = 31398174203566229210665534094126601315683074641013205440476552584312112883638278390105806127975406224783128340041129316782549009811196493319665336016690985557862367551545487842904828051293613836275987595871004601968935866634955528775536847402581734910742403788941725304146192149165731194199024154454952157531068881114411265538547462017207361362857 for i in range (2 ^ 20 ): g = g1 ^^ i if GCD(n, g) == g: print (g) break
1 2 3 4 5 6 7 8 9 10 g = 228679177303871981036829786447405216349 q = n // g phi_n = (g - 1 ) * (q - 1 ) c = 20920247107738496784071050239422540936224577122721266141057957551603705972966457203177812404896852110975768315464852962210648535130235298413611598658659777108920014929632531307409885868941842921815735008981335582297975794108016151210394446009890312043259167806981442425505200141283138318269058818777636637375101005540308736021976559495266332357714 d = inverse(e, phi_n) flag = pow (c,d,n) print (type (flag))print (long_to_bytes(int (flag)))
wiki-NTRUEncrypt 截图
