养成杯2021

Contents

养成杯2021

RSA?

 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 import os from Crypto.Util.number import * flag = "GWHT{xxxxxxxxx}" p = getPrime(256) q = getPrime(256) n = p*q N = (p-1)*(q-1) e = 65537 Mx = bytes_to_long(os.urandom(30)) My = bytes_to_long(flag) Z1 = (Mx*My)%n inv_Z1 = inverse_mod(Z1, n) inv_2 = inverse_mod(2, n) X = ((Z1+inv_Z1)*inv_2)%n Y = My inv_Y = inverse_mod(Y, n) a = ((inv_Z1-X)*inv_Y)%n D = (a*a)%n xy = lambda (x1,y1),(x2,y2) : ((x1*x2+D*y1*y2)%n, (x1*y2+x2*y1)%n) def getloop((x,y), e): ret = (x, y) for i in range(e-1): ret = xy(ret, (x,y)) return ret print n print getloop((X, Y), e) print a # 13390709926509813526471364597371124446888078365567927211781799241724742352679484983709219580483800891886832613684875066109177882219522305348565532970795023 # (5404548088049249951619519701935576492239293254135836357417714329205323074367876875480850741613547220698045360461761929952847796420174204143917852624050110, 2110372753170830610718226848526649992911771424441223687775304654852191999130502986109306355582366065947895295520226816523397652918227241733632791793362785) # 1762039418842677123086894939949574689744108610561557889235294034870342076452734215004689409493802437034960516295735815195656138656970901855976802991519141

$X=\frac{1+M_x^2M_y^2}{2M_xM_y}$

$Y=M_y$

$a=\frac{1-M_x^2M_y^2}{2M_xM_y^2}$

$D=\frac{(1-M_x^2M_y^2)^2}{4M_x^2M_y^4}$

n=0时

$X_0=\frac{1+M_x^2M_y^2}{2M_xM_y}$

$Y_0=M_y$

n=1时

$X_1=\frac{1+M_x^4M_y^4}{2M_x^2M_y^2}$

$Y_1=\frac{1+M_x^2M_y^2}{M_x}$

$Y_1a=\frac{1-M_x^4M_y^4}{2M_x^2M_y^2}$

$X_1-Y_1a=\frac{2M_x^4M_y^4}{2M_x^2M_y^2}=M_x^2M_y^2$

$X_0-Y_0a=\frac{2M_x^2M_y^2}{2M_xM_y}=M_xM_y$

 1 2 3 4 5 def getloop((x,y), e): ret = (x, y) for i in range(e-1): ret = xy(ret, (x,y)) return ret

solve

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 import libnum, gmpy2 n = 13390709926509813526471364597371124446888078365567927211781799241724742352679484983709219580483800891886832613684875066109177882219522305348565532970795023 p = 115718235064789220654263009993128325569382592506655305434488398268608329541037 q = n//p e = 65537 Xn, Yn = 5404548088049249951619519701935576492239293254135836357417714329205323074367876875480850741613547220698045360461761929952847796420174204143917852624050110, 2110372753170830610718226848526649992911771424441223687775304654852191999130502986109306355582366065947895295520226816523397652918227241733632791793362785 a = 1762039418842677123086894939949574689744108610561557889235294034870342076452734215004689409493802437034960516295735815195656138656970901855976802991519141 c = (Xn - Yn * a)%n d = gmpy2.invert(e,(p-1)*(q-1)) xy = pow(c,d,n) flag = ((1-xy*xy)*gmpy2.invert(2,n)*gmpy2.invert(xy,n)*gmpy2.invert(a,n))%n print(libnum.n2s(flag))

GWHT{pell_equation_is_very_interesting}