密码学实验

密码学实验

这是现代密码学配套实验,可以在实验中加深对现代密码学的了解,也可以加强自己的编程能力。

实验三

1.RSA加密时,存在某些e和m使得m^e mod n=m。现在在给定的 p=1009,q=3643,找出所有e,满足1<e<φ(1009,3643)且gcd(e,φ)=1,并且此时未加密信息的数目为最小值。求出所有这些e的和。
2.自己编写函数根据RSA流程完成字符串加密,并且对字符串进行处理
3.对给出的21个Frame,使用不同的RSA攻击方法破解出明文。(2016年密码数学挑战赛的赛题三)


第一题,套用计算隐藏消息数的公式[gcd(e -1,p -1)+1] [gcd(e -1,q -1)+1]即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#-*-coding:utf-8 -*-
def gcd(a, b):
while b:
a, b = b, a % b
return a
p, q, s, e = 1009, 3643, 0, 3
phi = (p-1) * (q-1)
#[gcd(e -1,p -1+1] [gcd(e -1,q -1+1]是公式,phi是偶数,为了让gcd(e, phi)==1成立,所以e必须是奇数,那么e-1必是偶数,q-1和p-1都为偶数,
#让gcd(e -1,p -1+1最小,即gcd(e-1, q-1)==2即可
while (e < phi):
if gcd(e, phi)==1 and gcd(e-1, q-1)==2 and gcd(e-1, p-1)==2:
s += e
e += 2
print ("Project Euler 182 Solution =", s)

第二题,手写一下RSA基本流程即可

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
# python 3.x
# Matasano Problem 39
# Implement RSA
import base64
import binascii #binascii模块包含很多在二进制和ASCII编码的二进制表示之间的转换方法
from Crypto.Util.number import getPrime

def generatePrime(bits):
return getPrime(bits); # 返回一个最大为 N bit的随机素数

def mypow(a, b, c): # returns a^b mod c
if (b == 0):
return 1
if (b == 1):
return (a % c)
b_bits = bin(b)[2:]
res = a;
for i in range(1, len(b_bits)):
res = res * res;
if (b_bits[i] == '1' ):
res = res * a;
res = res % c;
return res;

rawToHexLUT = ['00', '01', '02', '03', '04', '05', '06', '07', '08', '09', '0a', '0b', '0c', '0d', '0e', '0f',
'10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '1a', '1b', '1c', '1d', '1e', '1f',
'20', '21', '22', '23', '24', '25', '26', '27', '28', '29', '2a', '2b', '2c', '2d', '2e', '2f',
'30', '31', '32', '33', '34', '35', '36', '37', '38', '39', '3a', '3b', '3c', '3d', '3e', '3f',
'40', '41', '42', '43', '44', '45', '46', '47', '48', '49', '4a', '4b', '4c', '4d', '4e', '4f',
'50', '51', '52', '53', '54', '55', '56', '57', '58', '59', '5a', '5b', '5c', '5d', '5e', '5f',
'60', '61', '62', '63', '64', '65', '66', '67', '68', '69', '6a', '6b', '6c', '6d', '6e', '6f',
'70', '71', '72', '73', '74', '75', '76', '77', '78', '79', '7a', '7b', '7c', '7d', '7e', '7f',
'80', '81', '82', '83', '84', '85', '86', '87', '88', '89', '8a', '8b', '8c', '8d', '8e', '8f',
'90', '91', '92', '93', '94', '95', '96', '97', '98', '99', '9a', '9b', '9c', '9d', '9e', '9f',
'a0', 'a1', 'a2', 'a3', 'a4', 'a5', 'a6', 'a7', 'a8', 'a9', 'aa', 'ab', 'ac', 'ad', 'ae', 'af',
'b0', 'b1', 'b2', 'b3', 'b4', 'b5', 'b6', 'b7', 'b8', 'b9', 'ba', 'bb', 'bc', 'bd', 'be', 'bf',
'c0', 'c1', 'c2', 'c3', 'c4', 'c5', 'c6', 'c7', 'c8', 'c9', 'ca', 'cb', 'cc', 'cd', 'ce', 'cf',
'd0', 'd1', 'd2', 'd3', 'd4', 'd5', 'd6', 'd7', 'd8', 'd9', 'da', 'db', 'dc', 'dd', 'de', 'df',
'e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'ea', 'eb', 'ec', 'ed', 'ee', 'ef',
'f0', 'f1', 'f2', 'f3', 'f4', 'f5', 'f6', 'f7', 'f8', 'f9', 'fa', 'fb', 'fc', 'fd', 'fe', 'ff',]


def hexToRaw(hx): #十六进制字符串转换为raw
raw = binascii.unhexlify(hx);
return raw;

def rawToHex(raw): #raw串转换为十六进制 raw原始字符串
#hx = binascii.hexlify(raw);
hx = '';
for r in raw:
if type(r) != int:
r = ord(r);
hx += rawToHexLUT[r];
return bytes(hx, 'UTF-8');


def egcd(a, b): #扩展欧几里得算法
if b == 0:
return (1, 0)
else:
q = a // b;
r = a % b;
(s, t) = egcd(b, r)
return (t, s - q * t)


def invmod(a, N): # Returns a^-1 mod N 乘法逆运算
(x, y) = egcd(a, N);
return x % N;


def rsa_demo1():
p = 71;
q = 77;
N = p*q;
et = (p-1)*(q-1);
e = 3;
assert((et%e) != 0);
d = invmod(e,et)
message = 42;
encrypted = mypow(message, e, N);
decrypted = mypow(encrypted, d, N);
assert(message == decrypted)
def rsa_demo2():
e = 3;
p = 4;
q = 4;
while ((p % e) == 1):
p = generatePrime(1024); #产生一个最大为 1024 bit的随机素数
while ((q % e) == 1):
q = generatePrime(1024); #产生一个最大为 1024 bit的随机素数
N = p*q;
phi = (p-1)*(q-1);
assert((phi%e) != 0);
d = invmod(e, phi);
message = 42;
encrypted = mypow(message, e, N);
decrypted = mypow(encrypted, d, N);
assert(message == decrypted);
rawMessage = b'May the Force be with you'
hexMessage = rawToHex(rawMessage);
intMessage = int(hexMessage, 16);
encrypted = mypow(intMessage, e, N);
decrypted = mypow(encrypted, d, N);
assert(intMessage == decrypted)
assert(hexToRaw(hex(intMessage)[2:]) == rawMessage);


if __name__ == "__main__":
rsa_demo1();
rsa_demo2();
print("success")

实验三,密码数学挑战赛原题,详见
2016密码挑战赛(RSA 加密体制破译)解题过程: https://blog.csdn.net/yangfan695695/article/details/80648086
RSA常见攻击方法: https://www.tr0y.wang/2017/11/06/CTFRSA/index.html

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
from gmpy2 import *
import pyfac
import re

n = []
e = []
c = []
m = {}
one = mpz(1)
two = mpz(2)

def get_m0():
e1 = mpz(int(e[0],16))
e2 = mpz(int(e[4],16))
n_ = mpz(int(n[0],16))
c1 = mpz(int(c[0],16))
c2 = mpz(int(c[4],16))
m_ = same_moudle(e1,e2,n_,c1,c2)
m["0&4"] = hex(m_)[-16:]

def china_residue():
index_ = [12,16,20]
c_ ={}
e_ = {}
n_ = {}
Mi = {}
M = mpz(1)
result = mpz(0)
for i in index_:
c_[i] = mpz(int(c[i],16))#int(c[i],16)
n_[i] = mpz(int(n[i],16))
for i in n_.values():
M =M* i
for i in index_:
Mi[i] = M / n_[i]
for i in index_:
e_[i] = invert(Mi[i],n_[i])
for i in index_:
result += Mi[i] * e_[i] * c_[i]
#print result
m_ = powmod(result,1,M)
m["3&8&12&16&20"] = hex(iroot(m_,5)[0])[-16:]

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m


def get_message():
for i in range(21):
with open("2/Frame{}".format(i)) as f:
m = f.read()
n.append(m[:256])
e.append(m[256:512])
c.append(m[512:768])

def same_moudle(e1,e2,n,c1,c2):
s2 = invert(e2,e1)
s1 = (one - e2 * s2) / e1
tem_result1 = pow(modinv(c1,n),-s1,n)
tem_result2 = pow(c2,s2,n)
result = tem_result1 * tem_result2
m = powmod(result,1,n)
return m

def fractor_crash():
index = [1,18]
n_ = []
q_ = []
et_ = []
d_ = []
e_ = []
c_ = []
m_ = []
for i in index:
n_.append(mpz(int(n[i],16)))
e_.append(mpz(int(e[i],16)))
c_.append(mpz(int(c[i],16)))
p = gcd(n_[0],n_[1])
for i in range(len(index)):
q_.append(n_[i] / p)
et_.append((q_[i] - one) * (p - one))
d_.append(invert(e_[i],et_[i]))
m_.append(hex(powmod(c_[i],d_[i],n_[i]))[-16:])
m["1"] = m_[0]
m["18"] = m_[1]


if __name__ == "__main__":
get_message()
get_m0() #0,4 共模攻击
china_residue() #3,8,12,16,20 低指数广播攻击
fractor_crash() ##1 18 因数碰撞

文章目录
  1. 1. 密码学实验
    1. 1.1. 实验三
,