from random import * from os import urandom from Crypto.Util.number import * defizprime(p): q=p-1 B=p.bit_length() K=0 while(q&1==0): q>>=1 K=K+1 print(q,K) for i in range(30): a=bytes_to_long(urandom(B%700))%p if( pow(a,q,p)==1or pow(a,q,p)==p-1): return1 E=q for j in range(K): E=(E*2)%p if(pow(a,E,p)==p-1): return1 return0 print(izprime(7878787629))
4： $$(\dfrac{2}{b})= \begin{cases} 1& b\equiv \text{1 or 7}\pmod 8\ -1& b\equiv \text{3 or 5}\pmod 8\end{cases}$$
程序代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
defisqr(x,p): if p==1or x==1: return1 sgn=1 while x%2==0: x=x//2 if p%8==3or p%8==5: sgn=-sgn if x<p: _tmp=p p=x x=_tmp if x%4==3and p%4==3 : sgn=-sgn return sgn*isqr(x%p,p)
from Crypto.Util.number import * defPollard_p_1(N): a = 2 whileTrue: f = a # precompute for i in range(1, 80000): f = pow(f, i, N) for i in range(80000, 104729+1): f = pow(f, i, N) if i % 15 == 0: d = GCD(f-1, N) if1 < d < N: return d print(a) a += 1
from __future__ import print_function import libnum
defcontinued_fractions_expansion(numerator,denominator):#(e,N) result=[] divident = numerator % denominator quotient = numerator // denominator result.append(quotient) while divident != 0: numerator = numerator - quotient * denominator tmp = denominator denominator = numerator numerator = tmp divident = numerator % denominator quotient = numerator // denominator result.append(quotient) return result defconvergents(expansion): convergents=[(expansion[0], 1)] for i in range(1, len(expansion)): numerator = 1 denominator = expansion[i] for j in range(i - 1, -1, -1): numerator += expansion[j] * denominator if j==0: break tmp = denominator denominator = numerator numerator = tmp convergents.append((numerator, denominator)) #(k,d) return convergents defnewtonSqrt(n): approx = n // 2 better = (approx + n // approx) // 2 while better != approx: approx = better better = (approx + n // approx) // 2 return approx defwiener_attack(cons, e, N): for cs in cons: k,d = cs if k == 0: continue phi_N = (e * d - 1) // k #x**2 - ((N - phi_N) + 1) * x + N = 0 a = 1 b = -((N - phi_N) + 1) c = N delta = b * b - 4 * a * c if delta <= 0: continue x1 = (newtonSqrt(delta) - b)//(2 * a) x2 = -(newtonSqrt(delta) + b)//(2 * a) if x1 * x2 == N: return [x1, x2, k, d]
if __name__ == "__main__": n = 147282573611984580384965727976839351356009465616053475428039851794553880833177877211323318130843267847303264730088424552657129314295117614222630326581943132950689147833674506592824134135054877394753008169629583742916853056999371985307138775298080986801742942833212727949277517691311315098722536282119888605701 e = 18437613570247445737704630776150775735509244525633303532921813122997549954741828855898842356900537746647414676272022397989161180996467240795661928117273837666615415153571959258847829528131519423486261757569454011940318849589730152031528323576997801788206457548531802663834418381061551227544937412734776581781 c = 140896698267670480175739817539898638657099087197096836734243016824204113452987617610944986742919793506024892638851339015015706164412994514598564989374037762836439262224649359411190187875207060663509777017529293145434535056275850555331099130633232844054767057175076598741233988533181035871238444008366306956934 expansion = continued_fractions_expansion(e, n) cons = convergents(expansion) p, q, k, d = wiener_attack(cons, e, n) m = pow(c, d, n) print(libnum.n2s(m))
assert(len(flag) % 16 == 0) c3 = cipher1.encrypt(flag) c4 = cipher2.encrypt(c3) print('Your flag:{}'.format(hexlify(c4))) ''' You have a chance to get something: UNCTF2020_Enjoy_Crypto~ Your cipher:b'01a4e429e76db218fa0eb18f03ec69c9200a2362d8b4d7ea46170ce698389bbd' Your flag:b'196cc94c2d685beb54beeaa14c1dc0a6f3794d65fca0d1a1274515166e4255ab367383092e42d774992f74bc138faaad' '''
from string import * from gmpy2 import * from Crypto.Util.number import * from Crypto.Cipher import AES pt=b"UNCTF2020_Enjoy_Crypto~" val = len(pt) % 16 ifnot val == 0: pt += b'\x00'*(16 - val) print(pt) s=printable GivenChiper='01a4e429e76db218fa0eb18f03ec69c9200a2362d8b4d7ea46170ce698389bbd' GivenChiper=long_to_bytes(int(GivenChiper,16)) Key1='0'*13 boxi=[] for i1 in s: for i2 in s: for i3 in s: Keyi=Key1+i1+i2+i3 cipher1 = AES.new(key=Keyi.encode(), mode=AES.MODE_ECB) f=cipher1.encrypt(pt) boxi+=[f] with open('data1.out', 'w') as f: #for i in range(10): for i in range(len(s)**3): if(i%25000==0): print(i) f.write(hex(bytes_to_long(boxi[i]))[2:]+'\n') Key2='0'*13 boxi=[] for i1 in s: for i2 in s: for i3 in s: Keyii=i1+i2+i3+Key2 cipher2 = AES.new(key=Keyii.encode(), mode=AES.MODE_ECB) f=cipher2.decrypt(GivenChiper) boxi+=[f] with open('data2.out', 'w') as f: for i in range(len(s)**3): if(i%25000==0): print(i) f.write(hex(bytes_to_long(boxi[i]))[2:]+'\n')
