0.前言
1.twin-primes-50
文件夹里的内容有encrypt.py，encrypted，key1,key2.四个文件 encrypt.py内容如下：
from Crypto.Util.number import *
import Crypto.PublicKey.RSA as RSA
import os
N = 1024
def getTwinPrime(N):
while True:
p = getPrime(N)
if isPrime(p+2):
return p
def genkey(N = 1024):
p = getTwinPrime(N)
q = getTwinPrime(N)
n1 = p*q
n2 = (p+2)*(q+2)
e = long(65537)
d1 = inverse(e, (p-1)*(q-1))
d2 = inverse(e, (p+1)*(q+1))
key1 = RSA.construct((n1, e, d1))
key2 = RSA.construct((n2, e, d2))
if n1 < n2:
return (key1, key2)
else:
return (key2, key1)
rsa1, rsa2 = genkey(N)
with open("flag", "r") as f:
flag = f.read()
padded_flag = flag + "\0" + os.urandom(N/8 - 1 - len(flag))
c = bytes_to_long(padded_flag)
c = rsa1.encrypt(c, 0)[0]
c = rsa2.encrypt(c, 0)[0]
with open("key1", "w") as f:
f.write("%d\n" % rsa1.n)
f.write("%d\n" % rsa1.e)
with open("key2", "w") as f:
f.write("%d\n" % rsa2.n)
f.write("%d\n" % rsa2.e)
with open("encrypted", "w") as f:
f.write("%d\n" % c)
这是rsa加密的变形，加密的整体流程如下
1.产生两个大素数，然后继续判断两个大素数分别加2是否是素数，如果是，输出这两个大素数
2.计算两个模数n1，n2，使用相同的e分别形成两个rsa加密系统，然后导出公钥成为key1，key2。
3.用两个公钥对明文加密两次，形成了encrypted文件 。
破解思路：
1.n1=p*q,n2=(p+2)*(q+2)=p*q+2*(p+q)+4=n1+2*(p+q)+4,可得p+q=(n2-n1-4)/2
2.两边同时乘p，得到p^2+n1=((n2-n1-4)/2)*p,移项之后为p^2-((n2-n1-4)/2)*p+n1=0，成为一元二次方程，使用求根公式解决
破解代码如下：
#coding:utf-8
from Crypto.Util.number import *
import Crypto.PublicKey.RSA as RSA
import gmpy2
with open('key1','rb+') as f:
n1=long(f.read().splitlines()[0])
with open('key2','rb+') as f:
n2=long(f.read().splitlines()[0])
with open('encrypted','rb+') as f:
cipher=long(f.read().splitlines()[0])
s = (n2 - n1 - 4L) / 2L
# p^2 - sp + n1 = 0
b,a,c=-s,1,n1
p=long((-b+gmpy2.isqrt(b**2-4*a*c))/(2*a))
q=n1/p
n1 = p*q
n2 = (p+2)*(q+2)
e = long(65537)
d1 = inverse(e, (p-1)*(q-1))
d2 = inverse(e, (p+1)*(q+1))
key1 = RSA.construct((n1, e, d1))
key2 = RSA.construct((n2, e, d2))
plain=key2.decrypt(cipher)
plain=key1.decrypt(plain)
print long_to_bytes(plain)
2.Easy-one
文件夹里的内容有encryptor.c，msg001，msg001.enc,msg002.enc.四个文件 encryptor.c内容如下：
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int main(int argc, char **argv) {
if (argc != 3) {
printf("USAGE: %s INPUT OUTPUT\n", argv[0]);
return 0;
}
FILE* input = fopen(argv[1], "rb");
FILE* output = fopen(argv[2], "wb");
if (!input || !output) {
printf("Error\n");
return 0;
}
char k[] = "CENSORED";
char c, p, t = 0;
int i = 0;
while ((p = fgetc(input)) != EOF) {
c = (p + (k[i % strlen(k)] ^ t) + i*i) & 0xff;
t = p;
i++;
fputc(c, output);
}
return 0;
}
加密的整体流程如下
1.第一个参数是要加密的文件，第二个参数是加密后输出的文件
2.使用密钥k对文件进行加密，加密公式为c = (p + (k[i % strlen(k)] ^ t) + i*i) & 0xff
3.输出
破解思路
1.首先根据msg001，msg001.enc，解出密钥k
2.根据msg002.enc，密钥解出明文。
破解代码如下：
cipher = open ("/.../msg001.enc","rb").read().strip()
plain = open("/.../msg001","rb").read().strip()
cipher =[ ord(i) for i in cipher]
plain =[ ord(i) for i in plain]
key = ""
i=t=0
for i in range(len(plain)):
c =((cipher[i] - i*i - plain[i])^t)&0xff
key+=chr(c)
t = plain[i]
print key
得到的结果为VeryLongKeyYouWillNeverGuessV，使用此密钥验证时发现最后一位的加密结果不同，猜测应该是V重复了，实际密钥为VeryLongKeyYouWillNeverGuess。再次验证，发现加密成功。
根据得到的key和msg002.enc，求解msg002，破解脚本如下：
cipher = open ("/.../msg002.enc","rb").read().strip()
cipher =[ ord(i) for i in cipher]
key='VeryLongKeyYouWillNeverGuess'
plain=''
key=[ord(i) for i in key]
i=p=t=0
for i in range(len(cipher)):
print hex(cipher[i])
p=(cipher[i]-i*i-(key[i%len(key)]^t))&0xff
t=p
plain+=chr(t)
with open("/.../msg002","wb+") as f:
f.write(plain)
得到明文为：
The known-plaintext attack (KPA) is an attack model for cryptanalysis where the attacker has samples of both the plaintext (called a crib), and its encrypted version (ciphertext). These can be used to reveal further secret information such as secret keys and code books. The term "crib" originated at Bletchley Park, the British World War II decryption operation.
The flag is CTF{6d5eba48508efb13dc87220879306619}
3.baby_rsa
查看文件baby_rsa的内容，如下：
p+q : 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
(p+1)(q+1) : 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
e : 0xe6b1bee47bd63f615c7d0a43c529d219
d : 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
enc_flag : 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a 很明显的rsa加密，需要求解一个模数n，n的求法如下：
(p+1)(q+1)=p*q+p+q+1
n=p*q=(p+1)(q+1)-(p+q)-1 可求得n，然后就可以解出flag，破解脚本如下： ~~~python #!/usr/bin/python from Crypto.Util.number import * import Crypto.PublicKey.RSA as RSA #p+q s1=0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
#(p+1)(q+1) s2=0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
e=0xe6b1bee47bd63f615c7d0a43c529d219
d=0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
enc_flag=0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a n=s2-s1-1
rsa=RSA.construct((n, e, d)) flag=rsa.decrypt(enc_flag) flag=long_to_bytes(flag) #flag{cc7490e-78ab-11e9-b422-8ba97e5da1fd} print flag ~~~
