前言：
這是第一屆BCNSCTF Write Up，覺得其中的CRYPTO有點東西。
CRYPTO
three days of light
hint：1.吉奧萬巴蒂斯塔貝拉索先生的密碼
打開檔案
⡹⡷⡩⡧⡋⠁⡗⡯⠁⠅⡯⡊⡨⡄⡠⡩⡯⡜⠄⠅⡓⡯⡳⡝⠉⡅⡑⡯⡢⠀⡘⡯⡍=
雖然和盲文有點差別，但還是丢去線上解密試一試，得到
IGYW{1g_15_zXtPY_l45c_Cm9ua_R0h_}
有flag的格式了，但本次比賽字首是BCNS，是以應該不是flag。
知道後續給出了hint，一查，原來就是維吉尼亞密碼。
雖然不知道密鑰，但可以根據flag的字首BCNS和加密表反推出密鑰。
由IGYW推到BCNS可以得到密鑰HELE，然後
方法1：
腦洞一下，這一題題目是three days of light，可以想到海倫凱勒，是以密鑰就是HELEN。
方法2：
根據IGYW{1g_15_zXtPY_l45c_Cm9ua_R0h_}，其中的15可以推測是is，是以ig這裡可能是it，g->t，密鑰是E。
解密後得到
flag：BCNS{1t_15_sTiLL_e45y_Ri9ht_N0w_}
Hill
題目描述： 密文：AUJPSOADUIWAAMYOKQNTRLKY 明文中包含BABYHILLS
給了一波學習資料：
http://www.practicalcryptography.com/ciphers/hill-cipher/
希爾加密的原理：
0-25 分别代表 A-Z
然後
密鑰 X 明文=密文（mod 26）
根據線性代數的知識，密鑰 = 明文的逆矩陣 X 密文（mod 26）
這裡的關鍵就是求明文的逆矩陣；
根據線性代數的知識，明文的逆矩陣等于明文的伴随矩陣除以明文的行列式
但是在 mod 26 的情況下，
“明文的逆矩陣等于明文的伴随矩陣除以明文的行列式”
等價于
“明文的逆矩陣等于明文的伴随矩陣乘以明文的行列式分之一”
而行列式分之一再 mod 26 下，是多少呢？
這裡用到模逆元的知識
即，行列式的逆 乘以 行列式 mod 26 = 1
這裡我們可以用循環求解法，在1 到 25 中檢查，是否有滿足上式的值；若沒有，則說明該行列式在 模 26 下，不可逆。
回到題目。已知密文AUJPSOADUIWAAMYOKQNTRLKY，已知明文BABYHILLS。不确定的是，明文對應的密文是哪
幾位。這就隻能每一種可能都試過來。一共有24-9+1=16種可能。由于其中某些明文組合在26模下不可逆，可以很快的排除。
最終可以得出，AUJPSOADU對應BABYHILLS，密鑰為ZXYXUABXL
随後找一個線上解密網站：
https://www.dcode.fr/hill-cipher
解密得到flag：BCNS{BABYHILLSISSOEASYAMAZING}
下面有python2的解密腳本，可以得到密鑰的逆矩陣，用來加密密文就可逆得明文
import numpy as np
from sympy import Matrix
import string
alphabet = string.ascii_uppercase
def convert2matrix(m, dimension):
for index, i in enumerate(m):
values = []
if index % dimension == 0:
for j in range(0, dimension):
values.append([alphabet.index(m[index + j])])
if index == 0:
m_mat = np.matrix(values)
else:
m_mat = np.hstack((m_mat, values))
return m_mat
if __name__ == '__main__':
m = 'BABYHILLS'
c = 'AUJPSOADU'
dimension = 3
unknown_c = 'AUJPSOADUIWAAMYOKQNTRLKY'
c = convert2matrix(c, dimension)
c = Matrix(c)
c_inv = c.inv_mod(26)
c_inv = c_inv.tolist()
m = convert2matrix(m, dimension)
m = np.matrix(m)
dec_key = m*c_inv
dec_key %= 26
print(dec_key)
common RSA
下載下傳得到公鑰、密文和一份加密程式的python檔案
from Crypto.Util.number import getPrime, isPrime
flag = 'BCNS{***************}'
nbits = 2048
gbits = 1000
g = getPrime(int(gbits))
while True:
a = getPrime(int(nbits * 0.5) - gbits)
p = 2 * g * a + 1
if isPrime(p):
break
while True:
b = getPrime(int(nbits * 0.5) - gbits)
q = 2 * g * b + 1
if p != q and isPrime(q):
break
N = p * q
e = 65537
def str2int(s):
return int(s.encode('hex'), 16)
with open('pubkey.txt', 'w') as f:
f.write(str(e) + '\n')
f.write(str(N) + '\n')
plain = str2int(flag)
c = pow(plain, e, N)
with open('cipher.txt', 'w') as f:
f.write(hex(c))
根據代碼可以發現，p和q有公因數2g。閱讀資料
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.1333&rep=rep1&type=pdf
其中
FIRST ATTACK中提到”random“ map x -> xN-1+3 mod N
還提到了 Pollard‘s ρ method。查得資料：
https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
其中提到
x 1 =g(x 1 ), x 2 =g(g(x 2 ))
以及
再結合之前RSA中取得x的函數g()
可以構造出腳本
def gcd(a, b):
while b:
a, b = b, a%b
return a
def mapx(x):
x=(pow(x,n-1,n)+3)%n
return x
n=69644253355211341008615731931191271543561813393696247872647539097731025139317192459673762307075757132731275549640230207811535392037009379332836127098146781189449492546683808479320523007723143785405879701283306018933152398604266492142756051136873859933147996788896957521617197775057903279308388992326687663758748948992848119757592382269444816110369971700359633107240730859791792812997850676268227113732924544521525542208093031654945144498947161490945574192619160232755434359345047007106918074866249874032126617535840975113183977657865128782107944872492079643737033408856349680277869350387092177233021240502747437806549
x1=x2=1
while True:
x1=mapx(x1)
x2=mapx(mapx(x2))
p=gcd(x1-x2,n)
if (p!=1):
print(p)
print(n/p)
break
運作後可得p和q的值，随後就是套路取私鑰d，然後解密RSA得到： BCNS{w4!Y0u_4r3_A_gen1u5!}