M0D1.TOP 主页总览分类标签简介
【自制】ComSec部分作业答案
|math
字数总计: 5.1k|阅读时长: 24 分钟

特别声明

本blog不可外传，禁止任何形式的转载

持续更新中，任何问题欢迎随时电邮

mdlw@m.scnu.edu.cn

P.S. 代码块开头如果有sage字样 说明是后缀名为.sage的文件，需要用sagemath运行

学前作业：C语言程序包GMP的使用

本作业是一项实践操作。GMP是一种非常著名的多精度算术的Library，本作业包括以下内容：

1、阅读浏览GMP的主页，了解GMP的使用，https://gmplib.org/

2、安装GMP包

3、写一个C/C++程序，调用GMP包中的函数完成以下工作：

a、生成两个随机的大素数p和q，分别有512比特长。

b、把p和q相乘，赋值为n。

c、求比n小且与n互素的整数的个数，记为euler，并输出：p、q、n和euler。

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
#include <iostream>
#include <cstdlib>
#include <math.h>
#include <fstream>
#include <gmpxx.h>
#include <gmp.h>
using namespace std;

int rep = 15;   //素数测试用值 


//output:两个512比特的素数p,q 
void gender(mpz_t p,mpz_t q){
	
	gmp_randstate_t state;
	gmp_randinit_default(state);


	while(1){
		mpz_urandomb(p,state,512);		
		if( mpz_probab_prime_p(p,rep) == 1 ){
			while(1){
				mpz_urandomb(q,state,512);
				if( mpz_probab_prime_p(q,rep) == 1 ){
					break;
				}
			}
			break;
		}		
	}
	return;
}

//input：两个素数 p，q 
//output:p*q的欧拉函数值euler
void euler_func(mpz_t euler,mpz_t p,mpz_t q){
	mpz_t one,pp,qq;          //1,(p-1),(q-1)
	
	mpz_inits(one,pp,qq,NULL);
	mpz_set_str(one,"1",10);
	mpz_sub(pp,p,one);
	mpz_sub(qq,q,one);
	
	mpz_mul(euler,pp,qq);
	
	return;
} 



int main(){

	mpz_t p,q,n,euler;
	mpz_inits(p,q,n,euler,NULL);
	

	gender(p,q);
	mpz_mul(n,p,q);
	euler_func(euler,p,q);
	
	
	mpz_out_str(stdout,10,p);
	cout<<endl<<endl;
	mpz_out_str(stdout,10,q);
	cout<<endl<<endl;
	mpz_out_str(stdout,10,n);
	cout<<endl<<endl;
	mpz_out_str(stdout,10,euler);
	cout<<endl<<endl;
	
	
	return 0;
 }

作业一：Miller-Rabin算法—编程题

Miller-Rabin算法是一种素性判定算法，输入一个整数，判定其是否素数。具体算法过程参考CINTA的第五章。因为时间不够，所以就不讲。要求大家自行阅读相关内容并编程实现该算法，并测试。建议使用C/C++、Python、Go、Rust等语言。

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
#include <iostream>
#include <cstdlib>
#include <math.h>
#include <fstream>
#include <gmpxx.h>
#include <gmp.h>
using namespace std;

int times = 15;   //米勒测试次数

//input:a是随机选取的基，n是要测试的整数，而q是整数满足n-1 = q*(2^k)
//output:如果n是合数，输出0，否则n可能是素数，输出1
bool MillerTest(mpz_t a,mpz_t q,mpz_t n){
	mpz_t x,nn;
	mpz_inits(x,nn,NULL);
	mpz_powm(x,a,q,n);
	mpz_sub_ui(nn,n,1);
	
	if(  mpz_cmp_ui(x,1) == 0  ||  mpz_cmp(x,nn) == 0  ){
		return 1;
	}
	
	
	while(mpz_cmp(nn,q)!=0){
		
		mpz_powm(x,x,x,n);
		mpz_mul_ui(q,q,2);
		
		if( mpz_cmp(x,nn) == 0 ){
			return 1;
		}
	}
	
	return 0;
}


//Input:整数n和米勒测试次数
//Output:如果n通过k次米勒测试，输出1，否则输出0
bool IsPrime(mpz_t n,int k){
	
	gmp_randstate_t state;
	gmp_randinit_default(state);
	

	
	mpz_t q,a,remin;
	mpz_inits(q,a,remin,NULL);
	mpz_sub_ui(q,n,1);
	
	
	while(mpz_cdiv_r_ui(remin,q,2) == 0){
		mpz_cdiv_q_ui(q,q,2);
	}
	
	
	//output: 2 ~ n-1 的随机数 a 
	for(int i = 0;i < k;i++){
		mpz_urandomm(a,state,n);  
		
		while(mpz_cmp_ui(a,2) <= 0){
			mpz_urandomm(a,state,n);						  
		}	
	}
	
	if(!MillerTest(a,q,n)){
		return 0;
	}
	
	return 1;

} 

int main(){
	
	mpz_t n;
	mpz_inits(n,NULL);

		
	gmp_randstate_t state;
	gmp_randinit_default(state);

	
	mpz_urandomb(n,state,256);
	
	
	if(IsPrime(n,times)){
		mpz_out_str(stdout,10,n);
		cout<<endl<<"is Prime"<<endl;	
	}
	else{
		mpz_out_str(stdout,10,n);
		cout<<endl<<"is not Prime"<<endl;
	}

/*	用gmp库自带函数测试
	if(mpz_probab_prime_p(n,times) == 1){
		cout<<endl<<"is Prime"<<endl;
	}
	else{
		cout<<endl<<"is not Prime"<<endl;
	}
*/	
	
	return 0;
}

作业二：AES相关

理解AES算法S-Box的生成原理，写一个程序，构造出AES的S-Box。

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
# xor == add == sub

#output:a*(x**(times)) , a是多项式
def inner_mul(a,times):
    if times == 0:
        return a
	elif a > 127:
    	a = a<<1
    	a = a % 256
    	a = a^27
    else:
        a = a<<1
        
        
    times = times - 1
    return inner_mul(a,times)

#input: a,b ∈ GF(2**8)
#output: a*b
def mul(a,b):
    result = 0
    bb = '{:08b}'.format(b)
    bb = bb[::-1]
    for i in range(8):
        if(bb[i] == '1'):
            result = result^inner_mul(a,i)
            
        else:
            pass
        
    return result


#input: 0 <= a <= 255
#output:a的二进制比特长度
def length(a):
    leng = 0
    while(a):
        a = a>>1
        leng = leng + 1
    return leng


#input:被除数a，除数b
#output: q = a/b , r = a % b
def division(a,b):
    len1=length(a)
    len2=length(b)
    len3=len1-len2

    if a<b:                   #被除数小于除数
        if len3==0:           #两个数的长度相同，则直接商1，余数是二者异或的结果
            return (1,a^b)
        else:
            return (0,a)      #如果被除数的位数小于除数，则商0，余数为a
                
    topBit=1                  
    topBit<<=(len1-1)
    b<<=len3                  #把b的位数扩充到和a一致

    quotient=0
    remainder=0

    for i in range(len3):
        quotient<<=1        
        if (topBit&a):      
            quotient^=1     
            a^=b
        else:
            a^=0
        topBit>>=1          
        b>>=1

        
    quotient<<=1            
    if a<b:
        remainder=a
    else:
        quotient^=1
        remainder=a^b

    return quotient,remainder    


#input:m>n
#output:gcd(m,n)
def gcd(m,n):
    while(n!=0):
        m,n=n,m%n
    return m


#input:m>n ,gcd(m,n) == 1
#output:inverse of n 
def xgcd(m,n):
    r0,r1,s0,s1=1,0,0,1
    while(n):
        qq,rr=division(m,n)
        q,m,n=qq,n,rr
        r0,r1=r1,r0^mul(q,r1)
        s0,s1=s1,s0^mul(q,s1)
    return s0


#代换
def substitution(inverse):

    inbit = '{:08b}'.format(inverse)
    inbit = inbit[::-1]

    temp = []
    for i in range(8):
        temp.append(int(inbit[i]))
    
    res = [0,0,0,0,0,0,0,0]
    #res = temp
    
    c = [1,1,0,0,0,1,1,0]
    result = 0
    for i in range(8):
        res[i] = temp[i]^temp[(i+4)%8]^temp[(i+5)%8]^temp[(i+6)%8]^temp[(i+7)%8]^c[i]
        result += res[i]*(2**i)
        

    
    return hex(result)
    


def creat_sbox():
    box = []
    sbox = 0x0
    
    for i in range(256):
        sbox=substitution(xgcd(283,i))     
        #283代表不可约多项式：x**8+x**4+x**3+x+1
        box.append(sbox)
        
    for j in range(256):
        print(box[j],end=' ')
        if (j+1)%16==0:
            print('\n')



#--------------main-----------------:
creat_sbox()

作业三：AES相关

不会


作业四：RSA编程

选择密文攻击

构造一个 c = (c*)^2 塞进去然后开根号就行了

m = 101

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
//g++ --std=c++11 dec_rsa.cpp dec.o -lgmp -no-pie
//./a.out

#include <iostream>
#include <gmp.h>
#include "dec.h"
#include <stdio.h>
using namespace std;

const char* N_str = "10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531469002933770824382865926730400902798743137187335810705309884635534159797732259520594337385186897629868362414475309001507719259272508669419676508606630823351242964205044695669333236417591";
const char* e_str = "10335071977839588495324343307012721241868030345867699233451500809021555989403028103743221782417440900848403102247012012875905268518785845678756696925714007988778268752026049276281025329038071087021446834856566687537729918372863729292015978809506607411711073716898691660211835403800810547133032654209857";
const char *c_star_s = "775789568255447714013247918834475198679653917741675336925599335265205597974556878796619688391490153400553690715156825186410083467239441867930362368759072824742512821423959166270736914130604102452801162684877374802075310241079026986641176079329871431448404341153307957496668749957011118721172866996397";

const char *m_test_s = "2";

//output: c = m^2e mod n
void creat_c_new(mpz_t c){
    
	mpz_t x,n;
	mpz_inits(x,n,NULL);
	mpz_set_str(x,c_star_s,10); //x = c_star = m^e mod n
	mpz_set_str(n,N_str,10);
	
	mpz_powm_ui(c,x,2,n);
	
}

int main(){
	
	mpz_t c,y;
	char *y_str;
	
	mpz_inits(c,y,NULL);
	creat_c_new(c);
	
	y_str = dec(c);       			//output: y = m^{2ed} mod n = m^2 mod n
	cout<<"m**2:"<<y_str<<endl<<"m:";
		
	mpz_set_str(y,y_str,10);		
	mpz_root(y,y,2);
	mpz_out_str(stdout,10,y);
	
    return 0;
}

作业五：RSA破解

Alice decides to use RSA with the public key N = 1889570071. In order to guard against transmission errors, Alice has Bob encrypt his message twice, once using the encryption exponent e1 = 1021763679 and once using the encryption exponent e2 = 519424709. Eve intercepts the two encrypted messages

c1 = 1244183534 and c2 = 732959706. Assuming that Eve also knows N and the two encryption exponents e1 and e2. Please help Eve recover Bob’s plaintext without finding a factorization of N.

题目大意就是：为了防止传输出错，Alice让Bob用不同的e加密明文两次

（这样Alice收到密文并解出来后比较发现如果两段明文不一致，就说明传输出错了）

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
import gmpy2 as gp
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)

n = 1889570071
c1 = 1244183534
c2 = 732959706
e1 = 1021763679
e2 = 519424709

s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
if s1<0:
	s1 = - s1
	c1 = gp.invert(c1, n)
elif s2<0:
	s2 = - s2
	c2 = gp.invert(c2, n)

m = pow(c1,s1,n)*pow(c2,s2,n) % n
print(m)
#1054592380

作业六：RSA相关（纸质版作业）

纸质版作业就不po出来了，简单的运算（误


选做题：RSA攻击1

RSA算法的使用一般要求每个不同的用户有一个独立的模数N。有天，Bob脑洞大开，认为似乎没有必要这样做。只需要一个模数N，然后给不同的用户分发不同的e和d就好了。可惜这种做法有严重的安全漏洞。
给定Alice的公钥（e1，N），Adv为了破解Alice的密文，他也注册一个公私钥对，得到(e2, d2, N)，然后他就可以巧妙地计算出Alice的解密私钥。注意：Adv得到的私钥不一定与Alice的相同，只是它确实可以解密。
（e1 =

44379563805854841580307748547737435172564831877127303051909203409873174780389273150966396080375621148040275710628408649117613085199533826455458312376264659153842853015345496268736337902730232293424031775369541079662258443836020140399047886828048837071536578243295077689245549921524765222192270061081366989243

,
N =
188115669939527035644766943794256836704505079895306601119938518634078379404429524926183546093986493443422022468844644307633083886388295943602507953702360632321739073592477683222131866451975315695813478098524853358977564134499058448438525811837376172990710150323209055804682074564005014776547535959114226010493

）

(e2 =

112465763139808984065405993827008716763974555200543206549100182421914260511395374512318119557311872118857352370325610769529155517454000609905909538235321637165438962672069969201523246380106126889874030417878823876408727390390051948217715186480658609481138938023687641185709391304878382079926539531855678365763

, d2 =

55881649455902117785162844948995531081646760354831350250450328774662614334096209227124014992837725793190883247171284132768863157972472923057215962250425474753160669444247876851199006665484502793278672692761545198268608005712388135980371518592854149756626148424994498979112285655516912703587302199972664162731

, N =

188115669939527035644766943794256836704505079895306601119938518634078379404429524926183546093986493443422022468844644307633083886388295943602507953702360632321739073592477683222131866451975315695813478098524853358977564134499058448438525811837376172990710150323209055804682074564005014776547535959114226010493

)

以下是用(e1, N)加密得到的密文，请给出明文（没有编码，是一个整数）：

166834578157098529809222592291594342260836191039081705782260506690911922650094691879568641873546447862853989518762075081785381252999566333779425586950217410876199240677942391128773211264433855236931134494842223272683014826519273429450763047329625425561073729238027952900168036140503255431512655421527963913597

请解释过程，给出明文及其解密用的私钥。


d =
72818963105077629740558410461847080457967247911531271148355717844840007560618118158503931879141520737129717539191898962908710378608064897528018640573684648011556192613882739251759874374669201358126911422986850885586463283920904391451268159684723197972233648239891580239064904439566608991520126027809037410483
m =

131


已知n,e,d 可以用以下方法分解n

∵ed=1+h(p−1)(q−1)\because ed=1+h(p-1)(q-1)
∴∀g<n\therefore \forall g < n ,有 ged−1=gh(p−1)(q−1)g^{ed-1} =g^{h(p-1)(q-1)}

∵ged−1=1 mod n∵ g^{ed-1} = 1\ mod\ n
∴pq≡ged−1−1≡0(mod n)\therefore pq \equiv g^{ed-1} -1 \equiv 0 (mod\ n)

令 k=ed−1k=ed-1 ,则:
pq≡gk−1≡(gk/2−1)(gk/2+1)≡0(modn)pq \equiv g^k -1 \equiv (g^{k/2} -1)(g^{k/2} +1) \equiv 0(mod n)

不难发现，如果 gk/2−1g^{k/2} -1 在 mod n下 如果等于p或者q,那么就可以分解n了.

持续分解(gk−1)=(gk1−1)(gk1+1)(gk2+1)…(gkn+1)(gk/2+1)(g^k -1)=(g^{k1} -1)(g^{k1} +1)(g^{k2} +1)…(g^{kn} +1)(g^{k/2}+1)

如果直到不能再分解那么说明失败 可以换一个 g 继续尝试. 如果成功,那么就说明找到了(gki−1g^{ki} -1 必须不为0)


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
import gmpy2
import random

#output:p,which is one factor of n
def getpq(n,e,d):
    while True:
        k = e * d - 1
        g = random.randint(0, n)
        while k%2==0:
            k=k//2
            temp=gmpy2.powmod(g,k,n)-1
            if gmpy2.gcd(temp,n)>1 and temp!=0:
                return gmpy2.gcd(temp,n)

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)

e1 = 44379563805854841580307748547737435172564831877127303051909203409873174780389273150966396080375621148040275710628408649117613085199533826455458312376264659153842853015345496268736337902730232293424031775369541079662258443836020140399047886828048837071536578243295077689245549921524765222192270061081366989243

c1 = 166834578157098529809222592291594342260836191039081705782260506690911922650094691879568641873546447862853989518762075081785381252999566333779425586950217410876199240677942391128773211264433855236931134494842223272683014826519273429450763047329625425561073729238027952900168036140503255431512655421527963913597

e2 = 112465763139808984065405993827008716763974555200543206549100182421914260511395374512318119557311872118857352370325610769529155517454000609905909538235321637165438962672069969201523246380106126889874030417878823876408727390390051948217715186480658609481138938023687641185709391304878382079926539531855678365763

d2 = 55881649455902117785162844948995531081646760354831350250450328774662614334096209227124014992837725793190883247171284132768863157972472923057215962250425474753160669444247876851199006665484502793278672692761545198268608005712388135980371518592854149756626148424994498979112285655516912703587302199972664162731

N = 188115669939527035644766943794256836704505079895306601119938518634078379404429524926183546093986493443422022468844644307633083886388295943602507953702360632321739073592477683222131866451975315695813478098524853358977564134499058448438525811837376172990710150323209055804682074564005014776547535959114226010493


p = getpq(N,e2,d2)
q = N//p
assert p*q == N

phi = (p-1)*(q-1)

s = egcd(phi,e1)
assert s[2]*e1%phi == 1

m = pow(c1,s[2],N)
print("d:")
print(s[2])
print("m:")
print(m)

选做题：RSA攻击2

在不分解n的前提下，求d。

给定：

e = 14058695417015334071588010346586749790539913287499707802938898719199384604316115908373997739604466972535533733290829894940306314501336291780396644520926473

n = 33608051123287760315508423639768587307044110783252538766412788814888567164438282747809126528707329215122915093543085008547092423658991866313471837522758159

说明过程。


低私钥指数攻击（e大d小，Wiener Attack）

phi(n)=(p−1)(q−1)=pq−(p+q)+1=N−(p+q)+1phi(n) = (p-1)(q-1) = pq-(p+q)+1 = N - (p+q)+1

∵p,q∵ p,q 非常大

∴pq>>p+q\therefore pq >> p+q

∴phi(n)≈N\therefore phi(n) \approx N

∵ed≡1modphi(n)\because ed \equiv 1 mod phi(n)

∴ed=1+k∗phi(n)\therefore ed = 1+k*phi(n)

∴ephi(n)−kd=1d∗phi(n)\therefore \frac{e}{phi(n)} - \frac{k}{d} = \frac{1}{d*phi(n)}

∵phi(n)≈N∵ phi(n) \approx N

∴eN−kd=1d∗phi(n)\therefore \frac{e}{N} - \frac{k}{d} = \frac{1}{d*phi(n)}

同样 d∗phi(n)d*phi(n) 很大

∴eN\therefore \frac{e}{N} 略大于 kd\frac{k}{d}

因为 e 和 N 知道，所以计算出 eN\frac{e}{N} 后，比它略小的 kd\frac{k}{d} 可以通过计算 $\frac{e}{N} $的连分数展开，依次算出这个分数的每一个渐进分数

由于eN\frac{e}{N} 略大于 kd\frac{k}{d} ，Wiener证明该攻击能精确覆盖 kd\frac{k}{d}


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
#sage 
def rational_to_contfrac(x,y):
    # Converts a rational x/y fraction into a list of partial quotients [a0, ..., an]
    a = x // y
    pquotients = [a]
    while a * y != x:
        x, y = y, x - a * y
        a = x // y
        pquotients.append(a)
    return pquotients

def convergents_from_contfrac(frac):
    # computes the list of convergents using the list of partial quotients
    convs = [];
    for i in range(len(frac)): convs.append(contfrac_to_rational(frac[0 : i]))
    return convs

def contfrac_to_rational (frac):
    # Converts a finite continued fraction [a0, ..., an] to an x/y rational.
    if len(frac) == 0: return (0,1)
    num = frac[-1]
    denom = 1
    for _ in range(-2, -len(frac) - 1, -1): num, denom = frac[_] * num + denom, num
    return (num, denom)

e = 14058695417015334071588010346586749790539913287499707802938898719199384604316115908373997739604466972535533733290829894940306314501336291780396644520926473

n = 33608051123287760315508423639768587307044110783252538766412788814888567164438282747809126528707329215122915093543085008547092423658991866313471837522758159

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

def mod_inv(a, m):
    g, x, _ = egcd(a, m)
    return (x + m) % m

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x
  
def crack_rsa(e, n):
    frac = rational_to_contfrac(e, n)
    convergents = convergents_from_contfrac(frac)
    
    for (k, d) in convergents:
        if k != 0 and (e * d - 1) % k == 0:
            
            phi = (e * d - 1) // k
            s = n - phi + 1
            # check if x*x - s*x + n = 0 has integer roots
            D = s * s - 4 * n
            if D >= 0:
                sq = isqrt(D)
                if sq * sq == D and (s + sq) % 2 == 0: return d

d = crack_rsa(e, n)
print(d)
#65537

选做题：攻击RSA模数

请分解：8419248954524000439721779172023134688983838205866625782151550834434276874684863239544369195264071670152656061813873751842115416791829324879655667191724512456544905595733991629887800889255133717212624547817690492648616532902257249552981800714896543008295153051040335475732125114592095784407296265046992475467

并说明为什么能分解。


p = 2901594209141588502650222215814396586003195843612160434765689337683632253922307845012747360431881459197582849873533200212023894921607275433777719963916949

q = 2901594209141588502650222215814396586003195843612160434765689337683632253922307845012747360431881459197582849873533200212023894921607275433777719963916383

原因是p，q相差过小，用yafu可以快速分解


作业七：Diffie-Hellman相关

Review questions：10.1

Problems：10.1 10.2 10.14

-----

攻击DH：

P =93450983094850938450983409623(模数)

G =93450983094850938450983409621（生成元）

Alice send: 45416776270485369791375944998

Bob Send: 15048074151770884271824225393

What is the shared key?


代码如下，原理是小步大步算法（CINTA有介绍），基本思想是用空间换时间

我的运存空间不够，所以算不出来答案

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
import gmpy2
def discreteLog(g,p,a):              	#离散对数，求 g^x=a mod p中的x
    table={}
    sq=gmpy2.isqrt(p-1)
    m=gmpy2.add(sq,1)       			#向上取整
    for i in range(m):
        k=-i*m
        y=gmpy2.powmod(g,k,p)
        mod=((a%p)*y)%p     			#baby
        table.update({mod:i})
    j=0
    while True:
        result=gmpy2.powmod(g,j,p)      #giant
        if result in table.keys():
            sa=m*table[result]+j
            return sa
            #return table[result],m     #将对应的下标返回
        else:
            j=j+1
        
        
p=93450983094850938450983409623
a=45416776270485369791375944998 
b=15048074151770884271824225393
x = discreteLog(-2,p,a)
#x=discreteLog(-2,p,b)
print(x)

作业八：椭圆曲线

10.12.

考虑椭圆曲线 E11(1,6)E_{11}(1,6)，即由 y2=x3+x+6y^2 = x^3 + x + 6 定义的曲线，其模数 p=11p = 11。确定 E11(1,6)E_{11}(1,6) 上所有的点。

10.14.

对 E11(1,6)E_{11}(1,6) 上的点 G=(2,7)G = (2,7) ，计算 2∗G2*G 到 13∗G13*G 的值

.sage：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#sage ecc.sage
p = 11
A = 1
B = 6
E = EllipticCurve(GF(p),[0,0,0,A,B])
#10.12
print("all points in E:")
print(E.points())


#10.14
G = E([2,7])
for i in range(2,14):  
	output = i*G
	print(i,"G:",output)

作业九：Hash

11.1.安全Hash函数需要具有哪些特性？

  • ①输入长度可变
  • ②输出长度固定
  • ③效率
  • ④抗原像攻击(单向性)
  • ⑤抗第二原像攻击(抗弱碰撞性)
  • ⑥抗碰撞攻击(抗强碰撞性)
  • ⑦伪随机性

11.2.弱抗碰撞和强抗碰撞之间的区别是什么？

弱抗碰撞性：对任何给定的分块x，找到满足 y != x 且 H(x) = H(y) 的 y 在计算上不可行。

强抗碰撞性：找到任何满足 H(x) = H(y) 的偶对(x,y)在计算上不可行。

区别是有没有“给定任意的x”这个条件

11.3.Hash函数中的压缩函数的作用是什么？

压缩函数将一个较长的、固定长度的输入处理后返回一个较短的、固定长度的输出。

11.7.给出海绵结构的定义

在海绵函数中，输入消息被分块为固定长度的分组。每个分组逐次作为每轮迭代的输入，同时上轮迭代的输出也反馈至下轮的迭代中，最终产生一组输出块。

海绵函数由三组参数定义：

f = 内部函数，用于处理每轮的输入分组

r = 输入分组的位长度，称其为位速率

pad = 填充算法

海绵函数允许输入长度和输出长度都可变。


作业十:MAC与认证加密

12.1.消息认证是为了对付哪些类型的攻击

1）伪装

2）内容修改：包括插入、删除、转换和修改

3）顺序修改：包括插入、删除和重新排序

4）计时修改：对消息的延时和重播


12.5.什么是消息认证码

它是消息和密钥的函数，它产生定长的值，以该值作为认证符


12.6.消息认证码和单向Hash函数之间的区别是什么?

通俗的说，消息认证码是带密钥的hash函数。
消息认证码可以使用单向hash函数来构造，也可以使用对称加密算法来构造，现在一般多使用前者。

哈希只保证数据的完整性，而MAC不仅保证完整性还保证认证性（确保消息是从我们想收到的对象发来的，而不是别的人）。

哈希码只是单纯对message做哈希，没有其他另外的输入，可以用来检查消息是否被更改。

MAC通常用私钥作为hash函数的输入，生成MAC，没有私钥的attacker不能生成对应MAC。


作业十一：数字签名

Review questions：13.2 13.3. 13.6

Problems: 13.6

13.2.数字签名应该具有哪些性质？

①它必须能验证签名者、签名日期和时间

②它必须能认证被签的消息内容

③签名应能由第三方仲裁，以解决争执

因此，数字签名具有认证功能


13.3.数字签名应满足哪些要求？

①签名必须是与消息相关的二进制位串

②签名必须使用发送方某些独有的信息

③产生数字签名比较容易

④识别和验证签名比较容易

⑤伪造数字签名在计算上是不可行的。无论是从给定的数字签名伪造信息，还是从给定的消息伪造数字签名，在计算上都是不可行的。

⑥保存数字签名的副本是可行的。


13.6.直接数字签名方法中会遇到哪些威胁?

方法的有效性依赖于发送方的私钥的安全性。如果发送方想否认以前曾发送过某条消息，那么他可以称其私钥已丢失或被盗用，其他人伪造了他的签名。

另一种可能的威胁是，X的私钥可能在时刻T被盗用，但攻击者可用X的签名签发一条消息并加盖一个在T或T之前的时间戳。


13.6.

(a)

显然 Zp∗Z_p^* 的群阶是 p-1

由费马小定理得

gp−1≡1mod   pg^{p-1} \equiv 1 \mod\ p

由题可知

gq≡1mod   pg^q \equiv 1 \mod\ p

由拉格朗日定理，不难证明：

有限群里元素的阶整除群的阶

注意到

q 是素数且 q ∣ (p−1)q\ |\ (p-1)

设g的阶是r

显然 r≤qr ≤ q 且 r∣(p−1)r | (p-1)

假设 r ＜ q

则 q=kr+cq = kr + c , c<rc < r

gkr=(gr)k≡1mod   pg^{kr} = (g^r)^k \equiv 1 \mod\ p

gq=gkr+c≡gc≡1mod   pg^q = g^{kr+c} \equiv g^c \equiv 1 \mod\ p

与 r 是 g 的阶 相矛盾

所以假设不成立

所以 r = q

即 g 的阶是q


(b)

由费马小定理

h(p−1)≡1 mod ph^{(p-1)} \equiv 1\ mod\ p

由题可知

g=h(p−1)/q mod pg = h^{(p-1)/q}\ mod\ p

即

gq≡h(p−1)≡1mod   pg^q \equiv h^{(p-1)} \equiv 1 \mod\ p

由拉格朗日定理，不难证明：

有限群里元素的阶整除群的阶

注意到

q 是 素数 且 q ∣ (p−1)q\ |\ (p-1)

设g的阶是r

显然 r≤qr ≤ q 且 r∣(p−1)r | (p-1)

假设 r ＜ q

则 q=kr+cq = kr + c , c<rc < r

gkr=(gr)k≡1mod   pg^{kr} = (g^r)^k \equiv 1 \mod\ p

gq=gkr+c≡gc≡1mod   pg^q = g^{kr+c} \equiv g^c \equiv 1 \mod\ p

与 r 是 g 的阶 相矛盾

所以假设不成立

所以 r = q

所以 g 的阶是q


（c）

由拉格朗日定理可知一共有

ϕ(q)=q−1=156\phi(q) = q-1 = 156 个生成元

每轮循环找到生成元的概率为：

p′=156/40192p' = 156/40192

用 ϵ=k\epsilon = k 表示 前 k - 1 次均取到非生成元，而第k次取到生成元

因此

P(ϵ=k)=(1−p′)k−1∗p′P(\epsilon = k) = (1-p')^{k-1}*p'

可见 ϵ\epsilon 服从几何分布

数学期望：

Eϵ=1/p′=40192/156E\epsilon = 1/p' = 40192/156

即为所求


(d)

p=O(21024)p = O(2^{1024})

q=O(2160)q = O(2^{160})

Eϵ=O(2160)E\epsilon = O(\sqrt{2^{160}})

不愿意，因为该算法不是一个多项式时间算法


(e)

156/40192

文章作者: 莫折眉
文章链接: https://m0d1.top/2021/09/26/comsechomework/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 M0D1.TOP！
crypto