GKCTF 2020

match 评论

CRYPTO

小学生的密码学

e(x)=11x+6(mod26)

密文：welcylk

（flag为base64形式）

仿射密码，解密公式：$m=11^{-1}(e(x)-6)\pmod {26}$

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
import base64
def affline_decode(cipher_text, a, b, m):
	plain_text = ''
	for i in cipher_text:
		if i in 'abcdefghijklmnopqrstuvwxyz':
			plain_text += chr(((ord(i)-ord('a'))-b)*gmpy2.invert(a,m) % m + ord('a'))
		else:
			plain_text += i
	print(plain_text)
    
m = affline_decode('welcylk', 11, 6, 26)
flag = base64.b64encode(m)

​

babycrypto

附件：encode.txt

已知：n，e，enc，p高位（1024-128）

RSA中的coppersmith攻击（已知p的高位攻击）

Sage脚本求p，q：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#Sage
from sage.all import *
n = 0xb119849bc4523e49c6c038a509a74cda628d4ca0e4d0f28e677d57f3c3c7d0d876ef07d7581fe05a060546fedd7d061d3bc70d679b6c5dd9bc66c5bdad8f2ef898b1e785496c4989daf716a1c89d5c174da494eee7061bcb6d52cafa337fc2a7bba42c918bbd3104dff62ecc9d3704a455a6ce282de0d8129e26c840734ffd302bec5f0a66e0e6d00b5c50fa57c546cff9d7e6a978db77997082b4cb927df9847dfffef55138cb946c62c9f09b968033745b5b6868338c64819a8e92a827265f9abd409359a9471d8c3a2631b80e5b462ba42336717700998ff38536c2436e24ac19228cd2d7a909ead1a8494ff6c3a7151e888e115b68cc6a7a8c6cf8a6c005L
p4 = 0xe4e4b390c1d201dae2c00a4669c0865cc5767bc444f5d310f3cfc75872d96feb89e556972c99ae20753e3314240a52df5dccd076a47c6b5d11b531b92d901b2b512aeb0b263bbfd624fe3d52e5e238beeb581ebe012b2f176a4ffd1e0d2aa8c4d3a2656573b727d4d3136513a931428b
#p去0的剩余位
e = 65537
pbits = 1024
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
#经过以上一些函数处理后，n和p已经被转化为10进制
if roots:        
	p = p4+int(roots[0]) 
	print("n: "+str(n))
	print("p: "+str(p))
	print("q: "+str(n//p))

再结合enc正常解出明文m即可。

Backdoor

p=k*M+(65537**a %M)

已知：RSA正常加密脚本，公钥文件pub.pem，base64加密密文文件flag.enc

公钥文件解析得n，e，密文文件base64解码处理得c

从 $p=kM+(65537^a \% M)$ 入手，查询了解到此式子为弱素数生成公式

弱素数生成公式参考：

https://asecuritysite.com/encryption/copper

https://medium.com/asecuritysite-when-bob-met-alice/so-what-was-the-problem-with-the-estonian-id-system-and-tpms-1ef02a9bde7f

强/弱素数定义：https://zh.wikipedia.org/wiki/%E5%BC%BA%E7%B4%A0%E6%95%B0

n的素数因子p是由此公式生成的，生成脚本在参考文章中已知：

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
from Crypto.Util import number

k=3
vals=39
a=12
M=1

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999]

for x in range(0, vals):
    M=M*primes[x]

p=k*M+(65537**a %M)
print('k=',k)
print('a=',a)
print('Number of prime numbers used=',vals)
print('======')

print('M=',M)
print('\nPrime=',p)

isp = number.isPrime(p)
if (isp==1):
	print('Value is prime')
else:
	print('Value is not prime')

$M$ 代表前 $x$ 项素数的乘积， $x$ 的可选值有5，16，39，71，80，126。在参数 $k$ 与 $a$ 取值不大的情况下，选取不同的 $x$ 值，得到的 $p$ 的位数不同。

根据已知的n为134位，预估p的位数不超过134/2=67位，可确定 $x$ 值取39，即

$M=962947420735983927056946215901134429196419130606213075415963491270$

参考得到的 $p$ 符合位数要求。

20200524190011

要得到正确的p值，尝试爆破 $k$ 与 $a$ ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
M=962947420735983927056946215901134429196419130606213075415963491270
n=15518961041625074876182404585394098781487141059285455927024321276783831122168745076359780343078011216480587575072479784829258678691739

for k in range(100):
	for a in range(100):
		p=k*M+(65537**a %M)
		if n%p==0:
			print('k=',k)
			print('a=',a)
			print('\nPrime=',p)
			isp = gmpy2.is_prime(p)
			if isp:
				print('Value is prime')
			else:
				print('Value is not prime')
			print('======')

结果：

20200524190241

易知两个结果分别为正确的p，q值~

再结合密文c正常解出明文m即可。