RSA 复杂题目¶
2018 Tokyo Western Mixed Cipher¶
题目给的信息如下所示：
- 每次交互可以维持的时间长度约为 5 分钟
- 每次交互中中n是确定的 1024 bit，但是未知， e 为 65537
- 使用 aes 加密了 flag，密钥和 IV 均不知道
- 每次密钥是固定的，但是 IV 每次都会随机
- 可以使用 encrypt 功能随意使用 rsa 和 aes 进行加密，其中每次加密都会对 aes 的 iv 进行随机
- 可以使用 decrypt 对随意的密文进行解密，但是只能知道最后一个字节是什么
- 可以使用 print_flag 获取 flag 密文
- 可以使用 print_key 获取 rsa 加密的 aes 密钥
本题目看似一个题目，实则是 3 个题目，需要分步骤解决。在此之前，我們準備好交互的函數
def get_enc_key(io): io.read_until("4: get encrypted keyn") io.writeline("4") io.read_until("here is encrypted key :)n") c=int(io.readline()[:-1],16) return c def encrypt_io(io,p): io.read_until("4: get encrypted keyn") io.writeline("1") io.read_until("input plain text: ") io.writeline(p) io.read_until("RSA: ") rsa_c=int(io.readline()[:-1],16) io.read_until("AES: ") aes_c=io.readline()[:-1].decode("hex") return rsa_c,aes_c def decrypt_io(io,c): io.read_until("4: get encrypted keyn") io.writeline("2") io.read_until("input hexencoded cipher text: ") io.writeline(long_to_bytes(c).encode("hex")) io.read_until("RSA: ") return io.read_line()[:-1].decode("hex")
GCD attack n¶
第一步我们需要把没有给出的 n 算出来，因为我们可以利用 encrypt 功能对我们输入的明文 x 进行 rsa 加密，那么可以利用整除的性质算 n
因为x ^ e = c mod n 所以 n | x ^ e - c
def get_n(io):
rsa_c,aes_c=encrypt_io(io,long_to_bytes(2))
n=pow(2,65537)-rsa_c
for i in range(3,6):
rsa_c, aes_c = encrypt_io(io, long_to_bytes(i))
n=primefac.gcd(n,pow(i,65537)-rsa_c)
return n
可以利用加密进行 check
def check_n(io,n): rsa_c, aes_c = encrypt_io(io, "123") if pow(bytes_to_long("123"), e, n)==rsa_c: return True else: return False
RSA parity oracle¶
利用 leak 的的最后一个字节，我们可以进行选择密文攻击，使用 RSA parity oracle 回复 aes 的秘钥
def guess_m(io,n,c): k=1 lb=0 ub=n while ub!=lb: print lb,ub tmp = c * gmpy2.powmod(2, k*e, n) % n if ord(decrypt_io(io,tmp)[-1])%2==1: lb = (lb + ub) / 2 else: ub = (lb + ub) / 2 k+=1 print ub,len(long_to_bytes(ub)) return ub
PRNG Predict¶
这里我们可以解密 flag 的16字节之后的内容了，但是前16个字节没有 IV 是解密不了的。这时我们可以发现，IV 生成使用的随机数使用了 getrandbits，并且我们可以获取到足够多的随机数量，那么我们可以进行 PRNG 的 predict，从而直接获取随机数
这里使用了一个现成的的 java 进行 PRNG 的 Predict
public class Main { static int[] state; static int currentIndex; 40huo public static void main(String[] args) { state = new int[624]; currentIndex = 0; // initialize(0); // for (int i = 0; i < 5; i++) { // System.out.println(state[i]); // } // for (int i = 0; i < 5; i++) { // System.out.println(nextNumber()); // } if (args.length != 624) { System.err.println("must be 624 args"); System.exit(1); } int[] arr = new int[624]; for (int i = 0; i < args.length; i++) { arr[i] = Integer.parseInt(args[i]); } rev(arr); for (int i = 0; i < 6240huo4; i++) { System.out.println(state[i]); } // System.out.println("currentIndex " + currentIndex); // System.out.println("state[currentIndex] " + state[currentIndex]); // System.out.println("next " + nextNumber()); // want -2065863258 } static void nextState() { // Iterate through the state for (int i = 0; i < 624; i++) { // y is the first bit of the current number, // and the last 31 bits of the next number int y = (state[i] & 0x80000000) + (state[(i + 1) % 624] & 0x7fffffff); // first bitshift y by 1 to the right int next = y >>> 1; // xor it with the 397th next number next ^= state[(i + 397) % 624]; // if y is odd, xor with magic number if ((y & 1L) == 1L) { next ^= 0x9908b0df; } // now we have the result state[i] = next; } } static int nextNumber() { currentIndex++; int tmp = state[currentIndex]; tmp ^= (tmp >>> 11); tmp ^= (tmp << 7) & 0x9d2c5680; tmp ^= (tmp << 15) & 0xefc60000; tmp ^= (tmp >>> 18); return tmp; } static void initialize(int seed) { // http://code.activestate.com/recipes/578056-mersenne-twister/ // global MT // global bitmask_1 // MT[0] = seed // for i in xrange(1,624): // MT[i] = ((1812433253 * MT[i-1]) ^ ((MT[i-1] >> 30) + i)) & bitmask_1 // copied Python 2.7's impl (probably uint problems) state[0] = seed; for (int i = 1; i < 624; i++) { state[i] = ((1812433253 * state[i - 1]) ^ ((state[i - 1] >> 30) + i)) & 0xffffffff; } } static int unBitshiftRightXor(int value, int shift) { // we part of the value we are up to (with a width of shift bits) int i = 0; // we accumulate the result here int result = 0; // iterate until we've done the full 32 bits while (i * shift < 32) { // create a mask for this part int partMask = (-1 << (32 - shift)) >>> (shift * i); // obtain the part int part = value & partMask; // unapply the xor from the next part of the integer value ^= part >>> shift; // add the part to the result result |= part; i++; } return result; } static int unBitshiftLeftXor(int value, int shift, int mask) { // we part of the value we are up to (with a width of shift bits) int i = 0; // we accumulate the result here int result = 0; // iterate until we've done the full 32 bits while (i * shift < 32) { // create a mask for this part int partMask = (-1 >>> (32 - shift)) << (shift * i); // obtain the part int part = value & partMask; // unapply the xor from the next part of the integer value ^= (part << shift) & mask; // add the part to the result result |= part; i++; } return result; } static void rev(int[] nums) { for (int i = 0; i < 624; i++) { int value = nums[i]; value = unBitshiftRightXor(value, 18); value = unBitshiftLeftXor(value, 15, 0xefc60000); value = unBitshiftLeftXor(value, 7, 0x9d2c5680); value = unBitshiftRightXor(value, 11); state[i] = value; } } }
写了一个 python 直接调用 java
from Crypto.Util.number import long_to_bytes,bytes_to_long
def encrypt_io(io,p):
io.read_until("4: get encrypted keyn")
io.writeline("1")
io.read_until("input plain text: ")
io.writeline(p)
io.read_until("RSA: ")
rsa_c=int(io.readline()[:-1],16)
io.read_until("AES: ")
aes_c=io.readline()[:-1].decode("hex")
return rsa_c,aes_c
import subprocess
import random
def get_iv(io):
rsa_c, aes_c=encrypt_io(io,"1")
return bytes_to_long(aes_c[0:16])
def splitInto32(w128):
w1 = w128 & (2**32-1)
w2 = (w128 >> 32) & (2**32-1)
w3 = (w128 >> 64) & (2**32-1)
w4 = (w128 >> 96)
return w1,w2,w3,w4
def sign(iv):
# converts a 32 bit uint to a 32 bit signed int
if(iv&0x80000000):
iv = -0x100000000 + iv
return iv
def get_state(io):
numbers=[]
for i in range(156):
print i
numbers.append(get_iv(io))
observedNums = [sign(w) for n in numbers for w in splitInto32(n)]
o = subprocess.check_output(["java", "Main"] + map(str, observedNums))
stateList = [int(s) % (2 ** 32) for s in o.split()]
r = random.Random()
state = (3, tuple(stateList + [624]), None)
r.setstate(state)
return r.getrandbits(128)
EXP¶
整体攻击代码如下：
from zio import * import primefac from Crypto.Util.number import long_to_bytes,bytes_to_long target=("crypto.chal.ctf.westerns.tokyo",5643) e=65537 def get_enc_key(io): io.read_until("4: get encrypted keyn") io.writeline("4") io.read_until("here is encrypted key :)n") c=int(io.readline()[:-1],16) return c def encrypt_io(io,p): io.read_until("4: get encrypted keyn") io.writeline("1") io.read_until("input plain text: ") io.writeline(p) io.read_until("RSA: ") rsa_c=int(io.readline()[:-1],16) io.read_until("AES: ") aes_c=io.readline()[:-1].decode("hex") return rsa_c,aes_c def decrypt_io(io,c): io.read_until("4: get encrypted keyn") io.writeline("2") io.read_until("input hexencoded cipher text: ") io.writeline(long_to_bytes(c).encode("hex")) io.read_until("RSA: ") return io.read_line()[:-1].decode("hex") def get_n(io): rsa_c,aes_c=encrypt_io(io,long_to_bytes(2)) n=pow(2,65537)-rsa_c for i in range(3,6): rsa_c, aes_c = encrypt_io(io, long_to_bytes(i)) n=primefac.gcd(n,pow(i,65537)-rsa_c) return n def check_n(io,n): rsa_c, aes_c = encrypt_io(io, "123") if pow(bytes_to_long("123"), e, n)==rsa_c: return True else: return False import gmpy2 def guess_m(io,n,c): k=1 lb=0 ub=n while ub!=lb: print lb,ub tmp = c * gmpy2.powmod(2, k*e, n) % n if ord(decrypt_io(io,tmp)[-1])%2==1: lb = (lb + ub) / 2 else: ub = (lb + ub) / 2 k+=1 print ub,len(long_to_bytes(ub)) return ub io = zio(target, timeout=10000, print_read=COLORED(NONE, 'red'),print_write=COLORED(NONE, 'green')) n=get_n(io) print check_n(io,n) c=get_enc_key(io) print len(decrypt_io(io,c))==16 m=guess_m(io,n,c) for i in range(m - 50000,m+50000): if pow(i,e,n)==c: aeskey=i print long_to_bytes(aeskey)[-1]==decrypt_io(io,c)[-1] print "found aes key",hex(aeskey) import fuck_r next_iv=fuck_r.get_state(io) print "##########################################" print next_iv print aeskey io.interact()
2016 ASIS Find the flag¶
这里我们以 ASIS 2016 线上赛中 Find the flag 为例进行介绍。
文件解压出来，有一个密文，一个公钥，一个 py 脚本。看一下公钥。
➜ RSA openssl rsa -pubin -in pubkey.pem -text -modulus Public-Key: (256 bit) Modulus: 00:d8:e2:4c:12:b7:b9:9e:fe:0a:9b:c0:4a:6a:3d: f5:8a:2a:94:42:69:b4:92:b7:37:6d:f1:29:02:3f: 20:61:b9 Exponent: 12405943493775545863 (0xac2ac3e0ca0f5607) Modulus=D8E24C12B7B99EFE0A9BC04A6A3DF58A2A944269B492B7376DF129023F2061B9
这么小的一个 N，先分解一下。
p = 311155972145869391293781528370734636009 q = 315274063651866931016337573625089033553
再看给的 py 脚本。
#!/usr/bin/python import gmpy from Crypto.Util.number import * from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_v1_5 flag = open('flag', 'r').read() * 30 def ext_rsa_encrypt(p, q, e, msg): m = bytes_to_long(msg) while True: n = p * q try: phi = (p - 1)*(q - 1) d = gmpy.invert(e, phi) pubkey = RSA.construct((long(n), long(e))) key = PKCS1_v1_5.new(pubkey) enc = key.encrypt(msg).encode('base64') return enc except: p = gmpy.next_prime(p**2 + q**2) q = gmpy.next_prime(2*p*q) e = gmpy.next_prime(e**2) p = getPrime(128) q = getPrime(128) n = p*q e = getPrime(64) pubkey = RSA.construct((long(n), long(e))) f = open('pubkey.pem', 'w') f.write(pubkey.exportKey()) g = open('flag.enc', 'w') g.write(ext_rsa_encrypt(p, q, e, flag))
逻辑很简单，读取 flag，重复 30 遍为密文。随机取 p 和 q，生成一个公钥，写入 pubkey.pem，再用脚本中的 ext_rsa_encrypt 函数进行加密，最后将密文写入 flag.enc。
尝试一下解密，提示密文过长，再看加密函数，原来当加密失败时，函数会跳到异常处理，以一定算法重新取更大的 p 和 q，直到加密成功。
那么我们只要也写一个相应的解密函数即可。
#!/usr/bin/python import gmpy from Crypto.Util.number import * from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_v1_5 def ext_rsa_decrypt(p, q, e, msg): m = bytes_to_long(msg) while True: n = p * q try: phi = (p - 1)*(q - 1) d = gmpy.invert(e, phi) privatekey = RSA.construct((long(n), long(e), long(d), long(p), long(q))) key = PKCS1_v1_5.new(privatekey) de_error = '' enc = key.decrypt(msg.decode('base64'), de_error) return enc except Exception as error: print error p = gmpy.next_prime(p**2 + q**2) q = gmpy.next_prime(2*p*q) e = gmpy.next_prime(e**2) p = 311155972145869391293781528370734636009 q = 315274063651866931016337573625089033553 n = p*q e = 12405943493775545863 # pubkey = RSA.construct((long(n), long(e))) # f = open('pubkey.pem', 'w') # f.write(pubkey.exportKey()) g = open('flag.enc', 'r') msg = g.read() flag = ext_rsa_decrypt(p, q, e, msg) print flag
拿到 flag
ASIS{F4ct0R__N_by_it3rat!ng!}
SCTF RSA1¶
这里我们以 SCTF RSA1 为例进行介绍，首先解压压缩包后，得到如下文件
➜ level0 git:(master) ✗ ls -al 总用量 4 drwxrwxrwx 1 root root 0 7月 30 16:36 . drwxrwxrwx 1 root root 0 7月 30 16:34 .. -rwxrwxrwx 1 root root 349 5月 2 2016 level1.passwd.enc -rwxrwxrwx 1 root root 2337 5月 6 2016 level1.zip -rwxrwxrwx 1 root root 451 5月 2 2016 public.key
尝试解压缩了一下 level1.zip 现需要密码。然后根据 level1.passwd.enc 可知，应该是我们需要解密这个文件才能得到对应的密码。查看公钥
➜ level0 git:(master) ✗ openssl rsa -pubin -in public.key -text -modulus Public-Key: (2048 bit) Modulus: 00:94:a0:3e:6e:0e:dc:f2:74:10:52:ef:1e:ea:a8: 89:d6:f9:8d:01:11:51:db:5e:90:92:48:fd:39:0c: 70:87:24:d8:98:3c:f3:33:1c:ba:c5:61:c2:ce:2c: 5a:f1:5e:65:b2:b2:46:91:56:b6:19:d5:d3:b2:a6: bb:a3:7d:56:93:99:4d:7e:4c:2f:aa:60:7b:3e:c8: fc:90:b2:00:62:4b:53:18:5b:a2:30:10:60:a8:21: ab:61:57:d7:e7:cc:67:1b:4d:cd:66:4c:7d:f1:1a: 2a:1d:5e:50:80:c1:5e:45:12:3a:ba:4a:53:64:d8: 72:1f:84:4a:ae:5c:55:02:e8:8e:56:4d:38:70:a5: 16:36:d3:bc:14:3e:2f:ae:2f:31:58:ba:00:ab:ac: c0:c5:ba:44:3c:29:70:56:01:6b:57:f5:d7:52:d7: 31:56:0b:ab:0a:e6:8d:ad:08:22:a9:1f:cb:6e:49: cc:01:4c:12:d2:ab:a3:a5:97:e5:10:49:19:7f:69: d9:3b:c5:53:53:71:00:18:60:cc:69:1a:06:64:3b: 86:94:70:a9:da:82:fc:54:6b:06:23:43:2d:b0:20: eb:b6:1b:91:35:5e:53:a6:e5:d8:9a:84:bb:30:46: b8:9f:63:bc:70:06:2d:59:d8:62:a5:fd:5c:ab:06: 68:81 Exponent: 65537 (0x10001) Modulus=94A03E6E0EDCF2741052EF1EEAA889D6F98D011151DB5E909248FD390C708724D8983CF3331CBAC561C2CE2C5AF15E65B2B2469156B619D5D3B2A6BBA37D5693994D7E4C2FAA607B3EC8FC90B200624B53185BA2301060A821AB6157D7E7CC671B4DCD664C7DF11A2A1D5E5080C15E45123ABA4A5364D8721F844AAE5C5502E88E564D3870A51636D3BC143E2FAE2F3158BA00ABACC0C5BA443C297056016B57F5D752D731560BAB0AE68DAD0822A91FCB6E49CC014C12D2ABA3A597E51049197F69D93BC5535371001860CC691A06643B869470A9DA82FC546B0623432DB020EBB61B91355E53A6E5D89A84BB3046B89F63BC70062D59D862A5FD5CAB066881 writing RSA key -----BEGIN PUBLIC KEY----- MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAlKA+bg7c8nQQUu8e6qiJ 1vmNARFR216Qkkj9OQxwhyTYmDzzMxy6xWHCzixa8V5lsrJGkVa2GdXTsqa7o31W k5lNfkwvqmB7Psj8kLIAYktTGFuiMBBgqCGrYVfX58xnG03NZkx98RoqHV5QgMFe RRI6ukpTZNhyH4RKrlxVAuiOVk04cKUWNtO8FD4vri8xWLoAq6zAxbpEPClwVgFr V/XXUtcxVgurCuaNrQgiqR/LbknMAUwS0qujpZflEEkZf2nZO8VTU3EAGGDMaRoG ZDuGlHCp2oL8VGsGI0MtsCDrthuRNV5TpuXYmoS7MEa4n2O8cAYtWdhipf1cqwZo gQIDAQAB -----END PUBLIC KEY-----
发现虽然说是 2048 位，但是显然模数没有那么长，尝试分解下，得到
p=250527704258269 q=74891071972884336452892671945839935839027130680745292701175368094445819328761543101567760612778187287503041052186054409602799660254304070752542327616415127619185118484301676127655806327719998855075907042722072624352495417865982621374198943186383488123852345021090112675763096388320624127451586578874243946255833495297552979177208715296225146999614483257176865867572412311362252398105201644557511678179053171328641678681062496129308882700731534684329411768904920421185529144505494827908706070460177001921614692189821267467546120600239688527687872217881231173729468019623441005792563703237475678063375349
然后就可以构造，并且解密，代码如下
from Crypto.PublicKey import RSA import gmpy2 from base64 import b64decode p = 250527704258269 q = 74891071972884336452892671945839935839027130680745292701175368094445819328761543101567760612778187287503041052186054409602799660254304070752542327616415127619185118484301676127655806327719998855075907042722072624352495417865982621374198943186383488123852345021090112675763096388320624127451586578874243946255833495297552979177208715296225146999614483257176865867572412311362252398105201644557511678179053171328641678681062496129308882700731534684329411768904920421185529144505494827908706070460177001921614692189821267467546120600239688527687872217881231173729468019623441005792563703237475678063375349 e = 65537 n = p * q def getprivatekey(n, e, p, q): phin = (p - 1) * (q - 1) d = gmpy2.invert(e, phin) priviatekey = RSA.construct((long(n), long(e), long(d))) with open('private.pem', 'w') as f: f.write(priviatekey.exportKey()) def decrypt(): with open('./level1.passwd.enc') as f: cipher = f.read() cipher = b64decode(cipher) with open('./private.pem') as f: key = RSA.importKey(f) print key.decrypt(cipher) #getprivatekey(n, e, p, q) decrypt()
发现不对
➜ level0 git:(master) ✗ python exp.py 一堆乱码。。
这时候就要考虑其他情况了，一般来说现实中实现的 RSA 都不会直接用原生的 RSA，都会加一些填充比如 OAEP，我们这里试试，修改代码
def decrypt1(): with open('./level1.passwd.enc') as f: cipher = f.read() cipher = b64decode(cipher) with open('./private.pem') as f: key = RSA.importKey(f) key = PKCS1_OAEP.new(key) print key.decrypt(cipher)
果然如此，得到
➜ level0 git:(master) ✗ python exp.py FaC5ori1ati0n_aTTA3k_p_tOO_sma11
得到解压密码。继续，查看 level1 中的公钥
➜ level1 git:(master) ✗ openssl rsa -pubin -in public.key -text -modulus Public-Key: (2048 bit) Modulus: 00:c3:26:59:69:e1:ed:74:d2:e0:b4:9a:d5:6a:7c: 2f:2a:9e:c3:71:ff:13:4b:10:37:c0:6f:56:19:34: c5:cb:1f:6d:c0:e3:57:3b:47:c4:76:3e:21:a3:b0: 11:11:78:d4:ee:4f:e8:99:2b:15:cb:cb:d7:73:e4: f9:a6:28:20:fd:db:8c:ea:16:ed:67:c2:48:12:6e: 4b:01:53:4a:67:cb:22:23:3b:34:2e:af:13:ef:93: 45:16:2b:00:9f:e0:4b:d1:90:c9:2c:27:9a:34:c3: 3f:d7:ee:40:f5:82:50:39:aa:8c:e9:c2:7b:f4:36: e3:38:9d:04:50:db:a9:b7:3f:4b:2a:d6:8a:2a:5c: 87:2a:eb:74:35:98:6a:9c:e4:52:cb:93:78:d2:da: 39:83:f3:0c:d1:65:1e:66:9c:40:56:06:0d:58:fc: 41:64:5e:06:da:83:d0:3b:06:42:70:da:38:53:e0: 54:35:53:ce:de:79:4a:bf:f5:3b:e5:53:7f:6c:18: 12:67:a9:de:37:7d:44:65:5e:68:0a:78:39:3d:bb: 00:22:35:0e:a3:94:e6:94:15:1a:3d:39:c7:50:0e: b1:64:a5:29:a3:69:41:40:69:94:b0:0d:1a:ea:9a: 12:27:50:ee:1e:3a:19:b7:29:70:b4:6d:1e:9d:61: 3e:7d Exponent: 65537 (0x10001) Modulus=C3265969E1ED74D2E0B49AD56A7C2F2A9EC371FF134B1037C06F561934C5CB1F6DC0E3573B47C4763E21A3B0111178D4EE4FE8992B15CBCBD773E4F9A62820FDDB8CEA16ED67C248126E4B01534A67CB22233B342EAF13EF9345162B009FE04BD190C92C279A34C33FD7EE40F5825039AA8CE9C27BF436E3389D0450DBA9B73F4B2AD68A2A5C872AEB7435986A9CE452CB9378D2DA3983F30CD1651E669C4056060D58FC41645E06DA83D03B064270DA3853E0543553CEDE794ABFF53BE5537F6C181267A9DE377D44655E680A78393DBB0022350EA394E694151A3D39C7500EB164A529A36941406994B00D1AEA9A122750EE1E3A19B72970B46D1E9D613E7D writing RSA key -----BEGIN PUBLIC KEY----- MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAwyZZaeHtdNLgtJrVanwv Kp7Dcf8TSxA3wG9WGTTFyx9twONXO0fEdj4ho7AREXjU7k/omSsVy8vXc+T5pigg /duM6hbtZ8JIEm5LAVNKZ8siIzs0Lq8T75NFFisAn+BL0ZDJLCeaNMM/1+5A9YJQ OaqM6cJ79DbjOJ0EUNuptz9LKtaKKlyHKut0NZhqnORSy5N40to5g/MM0WUeZpxA VgYNWPxBZF4G2oPQOwZCcNo4U+BUNVPO3nlKv/U75VN/bBgSZ6neN31EZV5oCng5 PbsAIjUOo5TmlBUaPTnHUA6xZKUpo2lBQGmUsA0a6poSJ1DuHjoZtylwtG0enWE+ fQIDAQAB -----END PUBLIC KEY-----
似乎还是不是很大，再次分解，然后试了 factordb 不行，试试 yafu。结果分解出来了。
P309 = 156956618844706820397012891168512561016172926274406409351605204875848894134762425857160007206769208250966468865321072899370821460169563046304363342283383730448855887559714662438206600780443071125634394511976108979417302078289773847706397371335621757603520669919857006339473738564640521800108990424511408496383 P309 = 156956618844706820397012891168512561016172926274406409351605204875848894134762425857160007206769208250966468865321072899370821460169563046304363342283383730448855887559714662438206600780443071125634394511976108979417302078289773847706397371335621757603520669919857006339473738564640521800108990424511408496259
可以发现这两个数非常相近，可能是 factordb 没有实现这类分解。
继而下面的操作类似于 level0。只是这次是直接解密就好，没啥填充，试了填充反而错
得到密码 fA35ORI11TLoN_Att1Ck_cL0sE_PrI8e_4acTorS。继续下一步，查看公钥
➜ level2 git:(master) ✗ openssl rsa -pubin -in public.key -text -modulus Public-Key: (1025 bit) Modulus: 01:ba:0c:c2:45:b4:5c:e5:b5:f5:6c:d5:ca:a5:90: c2:8d:12:3d:8a:6d:7f:b6:47:37:fb:7c:1f:5a:85: 8c:1e:35:13:8b:57:b2:21:4f:f4:b2:42:24:5f:33: f7:2c:2c:0d:21:c2:4a:d4:c5:f5:09:94:c2:39:9d: 73:e5:04:a2:66:1d:9c:4b:99:d5:38:44:ab:13:d9: cd:12:a4:d0:16:79:f0:ac:75:f9:a4:ea:a8:7c:32: 16:9a:17:d7:7d:80:fd:60:29:64:c7:ea:50:30:63: 76:59:c7:36:5e:98:d2:ea:5b:b3:3a:47:17:08:2d: d5:24:7d:4f:a7:a1:f0:d5:73 Exponent: 01:00:8e:81:dd:a0:e3:19:28:e8:ee:51:11:08:c7: 50:5f:61:31:05:d2:e2:ff:9b:83:71:e4:29:c2:dd: 92:70:65:d4:09:6d:58:c3:76:31:07:f1:d4:fc:cf: 2d:b3:0a:6d:02:7c:56:61:7c:be:7e:0b:7e:d9:22: 28:66:9e:fb:3d:2f:2c:20:59:3c:21:ef:ff:31:00: 6a:fb:a7:68:de:4a:0a:4c:1a:a7:09:d5:48:98:c8: 1f:cf:fb:dd:f7:9c:ae:ae:0b:15:f4:b2:c7:e0:bc: ba:31:4f:5e:07:83:ad:0e:7f:b9:82:a4:d2:01:fa: 68:29:6d:66:7c:cf:57:b9:4b Modulus=1BA0CC245B45CE5B5F56CD5CAA590C28D123D8A6D7FB64737FB7C1F5A858C1E35138B57B2214FF4B242245F33F72C2C0D21C24AD4C5F50994C2399D73E504A2661D9C4B99D53844AB13D9CD12A4D01679F0AC75F9A4EAA87C32169A17D77D80FD602964C7EA5030637659C7365E98D2EA5BB33A4717082DD5247D4FA7A1F0D573 writing RSA key -----BEGIN PUBLIC KEY----- MIIBIDANBgkqhkiG9w0BAQEFAAOCAQ0AMIIBCAKBgQG6DMJFtFzltfVs1cqlkMKN Ej2KbX+2Rzf7fB9ahYweNROLV7IhT/SyQiRfM/csLA0hwkrUxfUJlMI5nXPlBKJm HZxLmdU4RKsT2c0SpNAWefCsdfmk6qh8MhaaF9d9gP1gKWTH6lAwY3ZZxzZemNLq W7M6RxcILdUkfU+nofDVcwKBgQEAjoHdoOMZKOjuUREIx1BfYTEF0uL/m4Nx5CnC 3ZJwZdQJbVjDdjEH8dT8zy2zCm0CfFZhfL5+C37ZIihmnvs9LywgWTwh7/8xAGr7 p2jeSgpMGqcJ1UiYyB/P+933nK6uCxX0ssfgvLoxT14Hg60Of7mCpNIB+mgpbWZ8 z1e5Sw== -----END PUBLIC KEY-----
发现私钥 e 和 n 几乎一样大，考虑 d 比较小，使用 Wiener's Attack。得到 d，当然也可以再次验证一遍。
➜ level2 git:(master) ✗ python RSAwienerHacker.py Testing Wiener Attack Hacked! ('hacked_d = ', 29897859398360008828023114464512538800655735360280670512160838259524245332403L) ------------------------- Hacked! ('hacked_d = ', 29897859398360008828023114464512538800655735360280670512160838259524245332403L) ------------------------- Hacked! ('hacked_d = ', 29897859398360008828023114464512538800655735360280670512160838259524245332403L) ------------------------- Hacked! ('hacked_d = ', 29897859398360008828023114464512538800655735360280670512160838259524245332403L) ------------------------- Hacked! ('hacked_d = ', 29897859398360008828023114464512538800655735360280670512160838259524245332403L) -------------------------
这时我们解密密文，解密代码如下
from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_v1_5, PKCS1_OAEP import gmpy2 from base64 import b64decode d = 29897859398360008828023114464512538800655735360280670512160838259524245332403L with open('./public.key') as f: key = RSA.importKey(f) n = key.n e = key.e def getprivatekey(n, e, d): priviatekey = RSA.construct((long(n), long(e), long(d))) with open('private.pem', 'w') as f: f.write(priviatekey.exportKey()) def decrypt(): with open('./level3.passwd.enc') as f: cipher = f.read() with open('./private.pem') as f: key = RSA.importKey(f) print key.decrypt(cipher) getprivatekey(n, e, d) decrypt()
利用末尾的字符串 wIe6ER1s_1TtA3k_e_t00_larg3 解密压缩包，注意去掉 B。至此全部解密结束，得到 flag。
2018 WCTF RSA¶
题目基本描述为
Description: Encrypted message for user "admin": <<<320881698662242726122152659576060496538921409976895582875089953705144841691963343665651276480485795667557825130432466455684921314043200553005547236066163215094843668681362420498455007509549517213285453773102481574390864574950259479765662844102553652977000035769295606566722752949297781646289262341623549414376262470908749643200171565760656987980763971637167709961003784180963669498213369651680678149962512216448400681654410536708661206594836597126012192813519797526082082969616915806299114666037943718435644796668877715954887614703727461595073689441920573791980162741306838415524808171520369350830683150672985523901>>> admin public key: n = 483901264006946269405283937218262944021205510033824140430120406965422208942781742610300462772237450489835092525764447026827915305166372385721345243437217652055280011968958645513779764522873874876168998429546523181404652757474147967518856439439314619402447703345139460317764743055227009595477949315591334102623664616616842043021518775210997349987012692811620258928276654394316710846752732008480088149395145019159397592415637014390713798032125010969597335893399022114906679996982147566245244212524824346645297637425927685406944205604775116409108280942928854694743108774892001745535921521172975113294131711065606768927 e = 65537 Service: http://36.110.234.253
这个题目现在已经没有办法在线获取 binary 了，现在得到的 binary 是之前已经下载好的，我们当时需要登录用户的 admin 来下载对应的 generator。
通过简单逆向这个 generator，我们可以发现这个程序是这么工作的
- 利用用户给定的 license（32 个字节），迭代解密某个固定位置之后的数据，每 32 个字节一组，与密钥相异或得到结果。
- 密钥的生成方法为
- k_1=key
- k_2 =sha256(k_1)
- ...
- k_n=sha256(k_{n-1})
其中，固定位置就是在找源文件 generator 中第二次出现 ENCRYPTED 的位置，然后再次偏移 32 个字节。
_ENCRYPT_STR = ENCRYPTED_STR; v10 = 0; ENCRYPTED_LEN = strlen(ENCRYPTED_STR); do { do ++v9; while ( strncmp(&file_contents[v9], _ENCRYPT_STR, ENCRYPTED_LEN) ); ++v10; } while ( v10 <= 1 ); v11 = &file_start_off_32[loc2 + ENCRYPTED_LEN]; v12 = loc2 + ENCRYPTED_LEN; len = file_size - (loc2 + ENCRYPTED_LEN) - 32; decrypt(&file_start_off_32[v12], &license, len); sha256_file_start(v11, len, &output); if ( !memcmp(&output, &file_contents[v12], 0x20u) ) { v14 = fopen("out.exe", "wb"); fwrite(v11, 1u, len, v14); fclose(v14); sprintf(byte_406020, "out.exe %s", argv[1]); system(byte_406020); }
同时，我们需要确保生成的文件的校验对应的哈希值恰好为指定的值，由于文件最后是一个 exe 文件，所以我们可以认为最后的文件头就是标准的 exe 文件，因此就不需要知道原始的 license 文件，进而我们可以编写 python 脚本生成 exe。
在生成的 exe 中，我们分析出程序的基本流程为
- 读取 license
- 使用 license 作为 seed 分别生成 pq
- 利用 p，q 生成 n，e，d。
其漏洞出现在生成 p，q 的方法上，而且生成 p 和 q 的方法类似。
我们如果仔细分析下生成素数的函数的话，可以看到每个素数都是分为两部分生成的
- 生成左半部分 512 位。
- 生成右半部分 512 位。
- 左右构成 1024 比特位，判断是不是素数，是素数就成功，不是素数，继续生成。
其中生成每部分的方式相同，方式为
sha512(const1|const2|const3|const4|const5|const6|const7|const8|v9) v9=r%1000000007
只有 v9 会有所变化，但是它的范围却是固定的。
那么，如果我们表示 p，q 为
p=a*2^{512}+b
q=c*2^{512}+d
那么
n=pq=ac*2^{1024}+(ad+bc)*2^{512}+bd
那么
n \equiv bd \bmod 2^{512}
而且由于 p 和 q 在生成时，a，b，c，d 均只有 1000000007 种可能性。
进而，我们可以枚举所有的可能性，首先计算出 b 可能的集合为 S，同时我们使用中间相遇攻击，计算
n/d \equiv b \bmod 2^{512}
这里由于 b 和 d 都是 p 的尾数，所以一定不会是 2 的倍数，进而必然存在逆元。
这样做虽然可以，然而，我们可以简单算一下存储空间
64*1000000007 / 1024 / 1024 / 1024=59
也就是说需要 59 G，太大了，，所以我们仍然需要进一步考虑
n \equiv bd \bmod 2^{64}
这样，我们的内存需求瞬间就降到了 8 G左右。我们仍然使用枚举的方法进行运算。
其次，我们不能使用 python，，python 占据空间太大，因此需要使用 c/c++ 编写。
枚举所有可能的 d 计算对应的值 n/d 如果对应的值在集合 S 中，那么我们就可以认为找到了一对合法的 b 和 d，因此我们就可以恢复 p 和 q 的一半。
之后，我们根据
n-bd=ac*2^{1024}+(ad+bc)*2^{512}
可以得到
\frac{n-bd}{2^{512}} = ac*2^{512}+ad+bc
\frac{n-bd}{2^{512}} \equiv ad+bc \bmod 2^{512}
类似地，我们可以计算出 a 和 c，从而我们就可以完全恢复出 p 和 q。
在具体求解的过程中，在求 p 和 q 的一部分时，可以发现因为是模 2^{64}，所以可能存在碰撞（但其实就是一个是 p，另外一个是q，恰好对称。）。下面我们就求得了 b 对应的 v9。
注意：这里枚举出来的空间大约占用 11 个 G（包括索引），所以请选择合适的位置。
b64: 9646799660ae61bd idx_b: 683101175 idx_d: 380087137 search 23000000 search 32000000 search 2b000000 search d000000 search 3a000000 search 1c000000 search 6000000 search 24000000 search 15000000 search 33000000 search 2c000000 search e000000 b64: 9c63259ccab14e0b idx_b: 380087137 idx_d: 683101175 search 1d000000 search 3b000000 search 7000000 search 16000000 search 25000000 search 34000000
其实，我们在真正得到 p 或者 q 的一部分后，另外一部分完全可以使用暴力枚举的方式获取，因为计算量几乎都是一样的，最后结果为
... hash 7000000 hash 30000000 p = 13941980378318401138358022650359689981503197475898780162570451627011086685747898792021456273309867273596062609692135266568225130792940286468658349600244497842007796641075219414527752166184775338649475717002974228067471300475039847366710107240340943353277059789603253261584927112814333110145596444757506023869 q = 34708215825599344705664824520726905882404144201254119866196373178307364907059866991771344831208091628520160602680905288551154065449544826571548266737597974653701384486239432802606526550681745553825993460110874794829496264513592474794632852329487009767217491691507153684439085094523697171206345793871065206283 plain text 13040004482825754828623640066604760502140535607603761856185408344834209443955563791062741885 hash 16000000 hash 25000000 hash b000000 hash 34000000 hash 1a000000 ... ➜ 2018-WCTF-rsa git:(master) ✗ python Python 2.7.14 (default, Mar 22 2018, 14:43:05) [GCC 4.2.1 Compatible Apple LLVM 9.0.0 (clang-900.0.39.2)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> p=13040004482825754828623640066604760502140535607603761856185408344834209443955563791062741885 >>> hex(p)[2:].decode('hex') Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/usr/local/Cellar/python@2/2.7.14_3/Frameworks/Python.framework/Versions/2.7/lib/python2.7/encodings/hex_codec.py", line 42, in hex_decode output = binascii.a2b_hex(input) TypeError: Odd-length string >>> hex(p)[2:-1].decode('hex') 'flag{fa6778724ed740396fc001b198f30313}'
最后我们便拿到 flag 了。
详细的利用代码请参见 ctf-challenge 仓库。
相关编译指令，需要链接相关的库。
g++ exp2.cpp -std=c++11 -o main2 -lgmp -lcrypto -pthread
参考¶
本页面的全部内容在 CC BY-NC-SA 4.0 协议之条款下提供，附加条款亦可能应用。