CRYPTO CTF 2021 writeup
Crypto問題が無いCTFもある中で、こういった暗号特化のCTFがあるのは本当にありがたいです。
Result
Writeup
warm-up
Mic Check 440solves 19pts
Read the Rules, check the mic and enter the flag!
問題サイトにあるRuleを読むと一番下にflagがありました。
CCTF{W3lc0me_t0_The_0ne&0nly_Crypt0_CTF_Mad3ـw1th_L0ve_f0r_Crypt0!}
easy
Farm 149solves 41pts
Explore the Farm very carefully!
ファイル：enc.txt, farm.sage
え、これeasy？というくらい、最初の問題にしては難しかったです。
farm.sageをそのままsagemathなどで実行すると、keyが64種類の式があるのに対し、pkeyがその64種類の内一つであることが予想できます。
pkey = key**5 + key**3 + key**2 + 1
とありますが、この計算方法はよく分かっていません。
pkeyが64通りしかないのでこれをbrute forceします。
flagをbase64encodeしてから、文字列encに付け足しています。flagの先頭は"CCTF{"と分かっているため、"CCT"をencryptさせencの先頭4文字"805c"になるpkeyを探します。base64では平文3bytesが符号後4bytesになるのを利用します。
これでpkeyが求まりました。次に、変数ALPHABETの内どれをencryptすればencのi文字目になるかbrute forceします。ALPHABET内を1文字ずつencryptさせ、enc[i]に合致すればbase64encodeのi文字目が分かります。
最後に、得られた文字列をbase64decodeでflagとなります。
import string, base64, math ALPHABET = string.printable[:62] + '\\=' F = list(GF(64)) def keygen(l): key = [F[randint(1, 63)] for _ in range(l)] #key = math.prod(key) # Optimization the key length :D return key def maptofarm(c): assert c in ALPHABET return F[ALPHABET.index(c)] def decrypt(msg, key): #pkeyの特定 m64 = base64.b64encode(msg) for pkey in key: enct = '' for m in m64: enct += ALPHABET[F.index(pkey * maptofarm(chr(m)))] if enct[:4] == "805c": #暗号化に使われたpkeyならここが一致する print(pkey) return pkey key = keygen(14) #keyの候補全て出す pkey = decrypt(b"CCTF{", key) print("pkey=",pkey) enc = "805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj" base64_enc = b"" for i in range(len(enc)): for m in ALPHABET: #何をencryptすればenc[i]になるのかbrute force if enc[i] == ALPHABET[F.index(pkey * maptofarm(m))]: base64_enc += m.encode() break print(base64.b64decode(base64_enc))
CCTF{EnCrYp7I0n_4nD_5u8STitUtIn9_iN_Fi3Ld!}
KeyBase 118solves 48pts
Recovering secrets is hard, but there is always some easy parts!
nc 01.cr.yp.toc.tf 17010
ファイル：keybase.py
AESのCBCモードの問題です。
keyの一部と任意の平文32bytesの暗号文の一部が隠されています。加えてivも不明です。
以降は以下のように定義します。
pt1, pt2 : 任意の平文の前半16bytes, 後半16bytes ct1, ct2 : ptの暗号文の前半16bytes, 後半16bytes k1, k2 : ct1,ct2をkeyによってdecryptした値。下図の赤い部分 enc_flag : flagの暗号文
i ) keyをbruteforceする
keyの隠されている部分は2bytesのみです。2562通りなのでbrute forceできますね。以降はkeyをbrute forceしている状態で考えていきます。
ii ) k2を求める
"\x00"*16+ct2を復号します。この際ivは何でもいいです。得られた平文をpt'1, pt'2とすると、暗号文の先頭16bytesとpt'2をxorすればk2となります。
iii) ct1を求める
求めたk2とpt2をxorするとct1になります。はじめにct1の一部が分かっているので、それと合致しないものは排除しても良いですね。
iv) k1を求める
ct1を復号します。この際ivは何でもいいです。得られた平文をpt'1とすると、ivとpt'1をxorすればk1となります。
v) ivを求める
求めたk1とpt1をxorすればサーバ側が使ったivが求まります。
vi) flagを求める
enc_flagを求めたivとbrute forceしているkeyで復号し、"CCTF{"が含まれているものを出力して終了です。
keyを求めるAESの問題なんて結構珍しいですね。
from Crypto.Cipher import AES from Crypto.Util.number import * import binascii key_t = "a2824541d7b87474f6c9b43d68d0" enc_a = "2031e2b4219ea750ba6a27f8dbe76555" fk = "dca4" enc = "374fccd3d532f29967b5c7a83972b7279aaf3866fd22298df1e66990fe9a4b1b" tmp = "0123456789abcdef" tmp_iv = b"A"*16 pl = b"a"*16 for k1 in tmp: print("k1=",k1) for k2 in tmp: for k3 in tmp: for k4 in tmp: key = key_t+k1+k2+k3+k4 # i ) #print(key) key = binascii.unhexlify(key.encode()) #print(key) cipher = AES.new(key, AES.MODE_CBC, tmp_iv) tmp_e = "00"*16+enc_a assert len(tmp_e)%32 == 0 pt = cipher.decrypt(binascii.unhexlify(tmp_e)) assert len(pt) == 32 pt2 = pt[16:] bx = bytes_to_long(pt2) # ii ) ct1 = bx^bytes_to_long(pl) # iii ) cipher = AES.new(key, AES.MODE_CBC, tmp_iv) ct1 = long_to_bytes(ct1) while len(ct1)%16 != 0: ct1 = b"\x00"+ct1 pt1 = cipher.decrypt(ct1) ax = bytes_to_long(pt1)^bytes_to_long(tmp_iv) # iv ) iv = long_to_bytes(ax^bytes_to_long(pl)) # v ) while len(iv) < 16: iv = b"\x00"+iv fipher = AES.new(key, AES.MODE_CBC, iv) flag = fipher.decrypt(binascii.unhexlify(enc)) # vi) if b"CCTF" in flag: print(flag)
CCTF{h0W_R3cOVER_7He_5eCrET_1V?}
Symbols 70solves 70pts
Oh, my eyes, my eyes! People still can solve this kind of cryptography? Mathematicians should love this one!
ファイル： Symbols.png
各文字がflagの1文字と該当していそうです。こんなフォントがないか探していると、チームメイトから連絡が。
これ多分わかったかもです
latexコマンドの頭文字をとると多分答えです
なぬ!? その通りでした。
ちゃんと研究してLatexで論文書いている人には造作の無いことだったのかもしれません。一方私は…。
CCTF{Play_with_LaTeX}
medium-easy
Rima 93solves 56pts
Sequences are known to be good solutions, but are they good problems?
ファイル：rima.py, g.enc, h.enc
複雑なことをしていますね。読み解いていきましょう。
大きく分けて3つあります。
A) 配列fを作る
flagを2進数にして各桁を配列fの一つの要素とします。その後先頭に0を加えます。
次に、配列fのindexの小さい方から大きい方へ、indexが一つ大きいものの値を足します。なので、配列fの要素は0か1か2になります。
B) 配列g,hを作る
まず、a,bを決めます。aはlen(f)より大きい最小の素数、bはaの次の素数になります。
gは、f[0]がa個、f[1]がa個、、、f[len(f)-1]がa個の配列になります。長さはlen(f)×aですね。
hは 、f[0]がb個、f[1]がb個、、、f[len(f)-1]がb個の配列になります。長さはlen(f)×bです。
配列fの要素をコピーしているので、配列g,hともに要素は0,1,2のどれかです。
次に、g,h を編集していきます。
cを(len(f)>>2)より大きい最小の素数とします。
gもhも同様に以下の事を行います。
まず配列の先頭に要素0をc個挿入します。つまり、len(g) = len(f)×a+c, len(h) = len(f)×b+cとなります。
その後、配列のindexの小さい方から大きい方へ、indexがcだけ大きいものの値を足します。なので、配列g,hの要素は0から4までになります。
C) g.enc, h.encに書く
配列g,hを5進数に見立ててlong_to_bytes()したものをそれぞれ書いて保存します。
では、これを元に戻しましょう。
C') 配列g,hの復元
g.enc, h.encをbytes_to_longして5進数にして、各桁を配列g,hの要素にします。これに時間かかります。
B') a,b,cを求める
この式を利用します。
len(g) = len(f)×a+c, len(h) = len(f)×b+c
まずcをbrute forceします。len(f) = gcd(len(g)-c, len(h)-c) となり、そこからa, bも求めることが出来ます。
ここで、nextprime(len(f) ) == a かつ nextprime(a) == b かつ nextprime(len(f)>>2) == c となれば正しいa,b,cであることが分かります。
a = 257, b = 263, c = 67でした！
A') 配列fの復元
配列gをf[0]がa個、f[1]がa個、、、f[len(f)-1]がa個の配列となるように戻します。
作る時の逆工程をするので、indexの大きい方からc個先の要素を引きます。hについても同様です。
これで、gはa個飛ばし、hはb個飛ばししたものがfになります。
作る時の逆工程をするので、indexの大きい方から1個先の要素を引き、配列fの復元が終わりました。
仕上げに配列fを2進数に見立ててlong_to_bytesすればflagとなります。
from Crypto.Util.number import * def nextPrime(n): while True: n += (n % 2) + 1 if isPrime(n): return n # C' G = open("g.enc","rb") GG = G.readlines() g = b"" for gt in GG: g += gt H = open("h.enc","rb") HH = H.readlines() h = b"" for ht in HH: h += ht G = bytes_to_long(g[:-1]) H = bytes_to_long(h[:-1]) g = [] h = [] while G != 0: g = [G%5] + g G //= 5 while H != 0: h = [H%5] + h H //= 5 lg = len(g) lh = len(h) #lg = len(f)*a + c #lh = len(f)*b + c import math # B' for c in range(lg): if isPrime(c): lf = math.gcd(lg-c,lh-c) a = (lg-c)//lf b = (lh-c)//lf if lf > 50 and isPrime(a) and isPrime(b): print("len(f)=",lf) print("a=",a) print("b=",b) print("c=",c) if nextPrime(lf) == a and nextPrime(a) == b and nextPrime(lf>>2) == c: print("Perfect!!!") break #g,hを逆に for i in range(len(g)-c-1,-1,-1): g[i] -= g[i+c] assert g[i] >= 0 for i in range(len(h)-c-1,-1,-1): h[i] -= h[i+c] assert h[i] >= 0 g = g[c:] h = h[c:] f = [] # A' for i in range(0,len(g),a): f.append(g[i]) for i in range(len(f)-2,-1,-1): f[i] -= f[i+1] assert f[i] >= 0 flag = ''.join(str(v) for v in f) print(flag) print(long_to_bytes(int(flag,2)))
CCTF{_how_finD_7h1s_1z_s3cr3T?!}
Hyper Normal 69solves 71pts
Being normal is hard these days because of Corona virus pandemic!
ファイル：hyper-normal.py, output.txt
ちょっとこれなんで解けたか怪しい部分があります。
outputの2重配列から、以下のことが分かります。
output[i][j] = (i+1)×chr(flagの何文字目)×(乱数0~126) mod 8443
chr(flagの何文字目)を32~127でbrute forceし、全てのiで乱数の部分が0~126になればOKです。
間違っている部分、考察不足があれば是非ともコメントいただきたいのですが、jがflagのj文字目に該当しているようでした。
これに気付くまではflagが何通りもなり得て意味のある文になるよう必死に探していたのですが、該当する文字が何列目か出すと、flagの何文字目かと一致するものが全部ありました。
でも途中でshuffleしているのは何…？
自分でもなんで解けたか分からなかったので伝わりにくくて申し訳ないです。
from Crypto.Util.number import * l = 55 p=8443 flag = [[] for _ in range(l)] cont = [] x = 0 aprj = [0 for _ in range(l)] while x < 5: ind = [[] for _ in range(l)] for i in range(l): #r0 * a = s0 mod p #a = (i+1)*ord(flag[i]) を求める for m in range(32,128): a = m*(i+1) for j in range(l): r0 = (enc[0][j]*inverse(a,p))%p if r0 < 127: ch = True for k in range(l): if k in cont: #ch = False continue r = (enc[k][j]*inverse(a,p))%p if r >= 127: ch = False break if ch: aprj[j] += 1 if i < len(tip): if tip[i] == chr(m): if not j in cont: cont.append(j) #if not [chr(m),j] in flag[i]: flag[i].append([chr(m),j]) else: flag[i].append([chr(m),j]) ind[i].append(j) if len(ind[i]) == 1: cont.append(ind[i][0]) x += 1 for k in cont: for i in range(len(flag)): if len(flag[i]) == 1: continue try: if flag[i][1] == k: flag = flag[:i] + flag[i+1:] break except: print("Except") print(flag[i]) for i in range(len(flag)): for j in range(len(flag[i])): if flag[i][j][1] == i: print(flag[i][j][0],end="") break print()
CCTF{H0w_f1Nd_th3_4lL_3I9EnV4Lu35_iN_FiN173_Fi3lD5!???}
Hamul 56solves 83pts
RSA could be hard, or easy?
ファイル：hamul.py, output.txt
まずこれが満たされる素数があるんだと問題ファイルを見て思いました。p,qが64bitsなのでこれらの積が分かれば素因数分解が出来るだろうと推測します。
筆算で考えると、nの下位x桁はp×qの下位x桁と一致し、nの上位y桁はp×qの上位y桁と一致します。
試してみると分かると思うのですが、これでp×qのほとんど桁が分かります。
手元でやってみたところ、問題ファイルのようにP,Qを決めるとx = 23, y=18程度であることが分かります。これで分からない桁数は0か1と判断し、(nの上位y桁)+[0-9]{0, 1}+(nの下位x桁)をsageなどで素因数分解し64bits素数の積になっているものを見つけます。
ちょっと手間取りましたが、これでp,qが求まりました。
from Crypto.Util.number import * n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043 c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399 primes = ['2', '3', '5', '7', '11', '13', '17', '19', '23', '29', '31', '37', '41', '43', '47', '53', '59', '61', '67', '71'] ns = [] for i in range(15,20): for j in range(18,23): N = int(str(n)[:i]+str(n)[-j:]) ch = True for p in primes: if N%int(p) == 0: #小さい素数で割れるものを排除 ch = False break if ch: ns.append(N) print(N) for k in range(10): N = int(str(n)[:i]+str(k)+str(n)[-j:]) #nの桁だけではpqが分からない場合 ch = True for p in primes: if N%int(p) == 0:#小さい素数で割れるものを排除 ch = False break if ch: ns.append(N) print(N) tmp = [[391111220047,25063748606238954787416469],[465963927380741639,21037493935292470637],[2647727654901734723 , 3702311783536219524841],[9324884768249686093 , 10512422984265378151],[2511932571814542137 , 39024587707209981139]] #大きい桁数×大きい桁数と素因数分解できた候補たち for t in tmp: p = int(str(t[0])+str(t[1])+str(t[1])+str(t[0])) if n%p == 0: print("Find!!!") print(p) print(n//p) q = n//p phi = (p-1)*(q-1) e = 65537 d = inverse(e,phi) m = pow(c,d,n) print(long_to_bytes(m))
はじめ、p×q = (nの上位y桁)+(nの下位x桁)だと思っていたので上手くいきませんでした
CCTF{wH3Re_0Ur_Br41N_Iz_5uP3R_4CtIVe_bY_RSA!!}
medium
Tuti 71solves 69pts
Cryptography is coupled with all kinds of equations very much!
ファイル：tuti.py
まあ気になるのはこれですよね
assert((x**2 + 1)*(y**2 + 1) - 2*(x - y)*(x*y - 1) == 4*(int(k, 16) + x*y))
式変形すると、このようになります。
(x^2+1)(y^2+1)-2(x-y)(xy-1) = 4k+4xy (x^2)(y^2)+x^2+y^2+1 -2((x^2)y-x-x(y^2)+y) - 4xy = 4k (x^2)(y^2-2y+1) + 2x(y^2-2y+1) +y^2-2y+1 = 4k ((y-1)^2)(x^2+2x+1) = 4k ((x+1)^2)((y-1)^2) = 4k
と、A2×B2 = 4kという形になりました。4kをfactorDBに投げると素因数分解できました。
あとは、得られた素数たちの部分集合を取ってその積をA、残りをBとして上式が成り立つか確認してx,yを求めます。
そして最後long_to_bytes()で終了です。
import gmpy2 from Crypto.Util.number import * k = (省略) k2, ch = gmpy2.iroot(k,2) fac = [2,3,11,11,19,47,71,3449,11953,5485619,2035395403834744453,17258104558019725087,1357459302115148222329561139218955500171643099] tt = 1 for h in fac: tt *= h assert tt == int(k2) s = pow(2,len(fac)) for i in range(s): tmp = bin(i)[2:] while len(tmp) < len(fac): tmp = "0"+tmp X = 1 for j in range(len(tmp)): if tmp[j] == "1": X *= fac[j] x = X-1 m1 = long_to_bytes(x) if b"CCTF" in m1: Y = 2*int(k2)//X y = Y+1 m2 = long_to_bytes(y) print(m1+m2)
CCTF{S1mPL3_4Nd_N!cE_Diophantine_EqUa7I0nS!}
Salt and Pepper 69solves 71pts
Salt and Pepper, Salty and Spicy! Can we attack these unnormalized served foods?
nc 02.cr.yp.toc.tf 28010
ファイル：salt_pepper.py
sha1とmd5のハッシュ値が与えられているので、逆引きできるかなと検索するもダメ。
Length Extention Attackでは？と気付いたチームメイトに全部やってもらいました。
実装には300行もかかったとのことで、有難い限りです。
Onlude 48solves 95pts
Encryption and Decryption could be really easy, while we expected the decryption to be harder!
ファイル：onlude.sage, output.txt
まずは式をまとめましょう。
S = L × U X = A + R Y = S × X = L × U × X = S × (A + R) = L × U × (A + R) E = L^(-1) × Y = U × X = U × (A + R)
そして、与えられた値は以下の通りです。
E L × U × L L^(-1) × S^2 × L R^(-1) × S^8
目標はAを求めることですが、慌てず求められる行列から求めていきましょう。
i) U
L^(-1) × S^2 × L = L^(-1) × (L × U) × (L × U) × L = U × L × U × L (U × L × U × L) × (L × U × L)^(-1) = U
ii) X
U^(-1) × E = U^(-1) × U × X = X
iii) S2
(L × U × L) × E × X^(-1) = L × U × L × L^(-1) × Y × X^(-1) = L × U × (S × X) × X^(-1) = S × S = S^2
iv) R
((R^(-1) × S^8) × (S^2)^(-4))^(-1) = (R^(-1) × S^8 × S^(-8))^(-1) = (R^(-1))^(-1) = R
v) A
X = A + R -> A = X - R
ということで、Aが求まりました。出力してみるとこんな感じです。
[48 0 0 0 0 57 0 0 0 0 66] [ 0 0 0 0 66 0 0 0 0 40 0] [ 0 0 0 4 0 0 0 0 13 0 0] [ 0 0 1 0 0 0 0 23 0 0 0] [ 0 26 0 0 0 0 51 0 0 0 0] [ 6 0 0 0 0 2 0 0 0 0 8] [ 0 0 0 0 45 0 0 0 0 25 0] [ 0 0 0 24 0 0 0 0 66 0 0] [ 0 0 66 0 0 0 0 5 0 0 0] [ 0 48 0 0 0 0 10 0 0 0 0] [ 1 0 0 0 0 65 0 0 0 0 0]
あとは0でない要素について、配列alphabetのindexを出力すればOKです。
global p, alphabet p = 71 alphabet = '=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>' def cross(m): return alphabet.index(m) def prepare(msg): A = zero_matrix(GF(p), 11, 11) for k in range(len(msg)): i, j = 5*k // 11, 5*k % 11 A[i, j] = cross(msg[k]) return A def keygen(): R = random_matrix(GF(p), 11, 11) while True: S = random_matrix(GF(p), 11, 11) if S.rank() == 11: _, L, U = S.LU() return R, L, U def encrypt(A, key): R, L, U = key S = L * U X = A + R Y = S * X E = L.inverse() * Y return E A = prepare(flag) key = keygen() R, L, U = key S = L * U E = encrypt(A, key) O = [[1,2],[3,4]] Et = [[25,55,61,28,11,46,19,50,37,5,21],[20,57,39,9,25,37,63,31,70,15,47],[56,31,1,1,50,67,38,14,42,46,14],[42,54,38,22,19,55,7,18,45,53,39],[55,26,42,15,48,6,24,4,17,60,64],[1,38,50,10,19,57,26,48,6,4,14],[13,4,38,54,23,34,54,42,15,56,29],[26,66,8,48,6,70,44,8,67,68,65],[56,67,49,61,18,34,53,21,7,48,32],[15,70,10,34,1,57,70,27,12,33,46],[25,29,20,21,30,55,63,49,11,36,7]] Kt = [[50,8,21,16,13,33,2,12,35,20,14],[36,55,36,34,27,28,23,21,62,17,8],[56,26,49,39,43,30,35,46,0,58,43],[11,25,25,35,29,0,22,38,53,51,58],[34,14,69,68,5,32,27,4,27,62,15],[46,49,36,42,26,12,28,60,54,66,23],[69,55,30,65,56,13,14,36,26,46,48],[25,48,16,20,34,57,64,62,61,25,62],[68,39,11,40,25,11,7,40,24,43,65],[54,20,40,59,52,60,37,14,32,44,4],[45,20,7,26,45,45,50,17,41,59,50]] Wt = [[34,12,70,21,36,2,2,43,7,14,2],[1,54,59,12,64,35,9,7,49,11,49],[69,14,10,19,16,27,11,9,26,10,45],[70,17,41,13,35,58,19,29,70,5,30],[68,69,67,37,63,69,15,64,66,28,26],[18,29,64,38,63,67,15,27,64,6,26],[0,12,40,41,48,30,46,52,39,48,58],[22,3,28,35,55,30,15,17,22,49,55],[50,55,55,61,45,23,24,32,10,59,69],[27,21,68,56,67,49,64,53,42,46,14],[42,66,16,29,42,42,23,49,43,3,23]] Qt = [[51,9,22,61,63,14,2,4,18,18,23],[33,53,31,31,62,21,66,7,66,68,7],[59,19,32,21,13,34,16,43,49,25,7],[44,37,4,29,70,50,46,39,55,4,65],[29,63,29,43,47,28,40,33,0,62,8],[45,62,36,68,10,66,26,48,10,6,61],[43,30,25,18,23,38,61,0,52,46,35],[3,40,6,45,20,55,35,67,25,14,63],[15,30,61,66,25,33,14,20,60,50,50],[29,15,53,22,55,64,69,56,44,40,8],[28,40,69,60,28,41,9,14,29,4,29]] E = zero_matrix(GF(p), 11, 11) for i in range(len(Et)): for j in range(len(Et[i])): E[i,j] = Et[i][j] K = zero_matrix(GF(p), 11, 11) #LUL for i in range(len(Kt)): for j in range(len(Kt[i])): K[i,j] = Kt[i][j] W = zero_matrix(GF(p), 11, 11) #L^-1SSL for i in range(len(Wt)): for j in range(len(Wt[i])): W[i,j] = Wt[i][j] Q = zero_matrix(GF(p), 11, 11) #R^-1S**8 for i in range(len(Qt)): for j in range(len(Qt[i])): Q[i,j] = Qt[i][j] U = W*(K.inverse()) X = U.inverse()*E S2 = K*E*(X.inverse()) Rinv = Q*((S2**4).inverse()) R = Rinv.inverse() A = X-R print("CCTF{",end="") for i in range(11): for j in range(11): if A[i, j] != 0: print(alphabet[A[i, j]],end="") print("}")
CCTF{LU__D3c0mpO517Ion__4L90?}
Unsolved
medium
Triplet 50solves 91pts
Fun with RSA, three times!
nc 07.cr.yp.toc.tf 18010
ファイル：Triplet.py
気になるところはこの部分
if 1 < e < min([phi_1, phi_2, phi_3]) and 1 < d < min([phi_1, phi_2, phi_3]): b = (e * d % phi_1 == 1) and (e * d % phi_2 == 1) and (e * d % phi_3 == 1)
phiが3つあって、それらを法とすると全て積が1になるedか…。素数を3つ生成して、2つの組み合わせが3組できるのでそれをphi_1~3にすればいいのでは？となりました。なので、
ed = 1 mod (p-1)(q-1)(r-1) ※p,q,rは生成する素数
ただ、e,dにもルールがあるので気を付けなければなりません。(p-1)(q-1)(r-1)+1を素因数分解して、ともに160bits以下になればいいのですが、何回試しても上手くいかずタイムアップ。
参考資料：
lior@wildboar:/2021-crypto-ctf/triplets# cd .. | lior5654’s CTF Writeups
これによると、p,q,r = kx+1の形にしていました。なるほど！
これで、lcm(phi_1~3) = lcm(k1,k2,k3) ≒ k1×k2×k3×xとなり、e,d ともに160bits以内に収まりました。
CCTF{7HrE3_b4Bie5_c4rRi3d_dUr1nG_0Ne_pr39naNcY_Ar3_triplets}
Ferman 31solves 134 pts
Modern cryptographic algorithms are the theoretical foundations and the core technologies of information security. Should we emphasize more?
nc 07.cr.yp.toc.tf 22010
(p-x)^2 + (q-y)^2 = k
の形をどう解いていいか分からず終了。結局sageに任せばいいなんて…。 kが7乗根持つのもヒントだったのかな？
