Summary

jrl Lv3
  2023-06-18 16:43:53 2023-06-18 16:43:53 Created   2023-07-26 18:40:30 2023-07-26 18:40:30 Updated    6.8k Words  28 Mins  

一 、RSA

1.1 What is RSA

1.1.1 Define RSA：

1977年，麻省理工学院的 Ron Rivest、Adi Shamir 和 Leonard Adleman 共同提出了一种非对称加密

算法，用他们三人的姓氏缩写命名为 RSA。RSA 既不是惟一，也不是最早的非对称加密算法。但它是使

用最广泛，因而也是最重要的非对称加密算法。

1.1.2 Basic principle：

eg：假设Alice和Bob要在网上进行加密通信，他们要怎么应用RSA来加密和解密信息呢？步骤如下：

1.随机选择两个不相同的素数 p , q。

2.将p , q 相乘，记为n = p × q 。

3.计算n的欧拉函数φ( n )，欧拉函数证明，当 p , q 为不相同的素数时，φ(n)=(p−1)(q−1) 。

4.随机选择一个整数 e ，满足两个条件：φ(n)与e互质,且1<e<φ(n) 。

5.计算e对于φ(n) 的模反元素d，也就是说找到一个d满足 ed = 1 mod φ(n)。这个式子等价于

ed−1=kφ(n)，实际上就是对于方程ed−kφ(n)=1求(d,k)的整数解。这个方程可以用扩展欧几里得算法求

解。

6.最终把(e,n)封装成公钥,(d,n)封装成私钥。

公钥与私钥的产生 ：

1.随机选择两个不同大质数 p 和 q，计算 N=p×q

2.根据欧拉函数，求得 φ(N)=φ(p)φ(q)=(p−1)(q−1)

3.选择一个小于 φ(N)φ(N) 的整数 e，使 e 和 φ(N)互质。并求得 e 关于 φ(N) 的模反元素，命名为 d，有

ed≡1(mod φ(N))

4.将 p 和 q 的记录销毁，此时，(N,e))是公钥，(N,d) 是私钥。

消息加密：

首先需要将消息 以一个双方约定好的格式转化为一个小于 N，且与 N 互质的整数 m。如果消息太长，

可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：

m^e≡c (mod N)

消息解密：

利用密钥d进行解密。

c^d≡m (modN)

正确性证明:

即我们要证m^ed≡m mod N，已知ed≡1 mod ϕ(N)，那么 ed=kϕ(N)+1，即需要证明

m^kϕ(N)+1≡m mod N

这里我们分两种情况证明

第一种情况 gcd(m,N)=1，那么 m^ϕ(N)≡1 mod N，因此原式成立。

第二种情况 gcd(m,N)≠1，那么 m 必然是 p 或者 q的倍数，并且 n=mn=m 小于 N。我们假设

m=xp

那么x必然小于 q，又由于q是素数。那么

m^{kϕ(N)+1}=m+uqm=m+uqxp=m+uxN

所以原式成立。

1.1.3 Summariz：

欧拉函数与小费马定理

(https://blog.csdn.net/weixin_30302609/article/details/96312617?ops_request_misc=%7B%22request%5Fid%22%3A%22166827222816782391833081%22%2C%22scm%22%3A%2220140713.130102334.pc%5Fall.%22%7D&request_id=166827222816782391833081&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-3-96312617-null-null.142

http://blog.csdn.net/boksic/article/details/6912381

1.2 Tools and third-party libaries

1.2.1 RSA-tool :

使用rsatool工具计算d的值，直接填入p,q,把e = 65537转换为16进制在再填入，再点击Calc.D,即可获得

D的值。在已知d的情况下，我们可以使用此工具将d分解为两个质数p,q，便于解出密文。但前提是已知

的d不是一个非常大的整数，因为大整数很难被分解。

1.2.2 Python :

Python中的第三方库中有许多有用的函数，通过调用不同的函数，可以进行高效的数学运算，这对于

RSA问题有极大的帮助，能大大提高破解的效率。

如 gmpy2

gmpy2.invert(x,m)求大整数x模m的逆元

print(gmpy2.invert(4, 23)) # eg:46 ≡ 1 mod 23 –> 6**gmpy2.powmod(x,y,m)求大整数x的y次幂模m取余

1.3 Eg analyze

1.3.1 Easy RSA:

from Geek Challenge 2022:

n=

6998481475728885783197750918520850086672477175656162927968781930122248321872866

3

e= 65537

c=

6767284506351741544248617509644866461758157956488531184232610787180559569745470

1

思路分析：

题目中给出了n,e,c

通过观察发现n较小，可以尝试将其分解为p,q，再调用gmpy.2函数解出d,进而解出flag

代码如下：

print(gmpy2.powmod(3, 3, 5)) # eg: 333 mod 5 –> 2

print(gmpy2.powmod(3, 2, 5)) # eg: 3*3 mod 5 –> 4

import gmpy2

import binascii

e = 65537从而解出flag:

b’SYC{5t4rt_R5A_ls_1t_3a5y?}’

1.3.2 Crypto–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
from Crypto.Util.number import *
import gmpy2 as gp

flag = b'xxxxxxxxx'
m=bytes_to_long(flag)

p = getPrime(1024)
q = getPrime(1024)
n = p*q*q
phi = q*(p-1)*(q-1)
e = 0x10001
d = gp.invert(e,phi)
c1 = gp.powmod(m,e,n)
c2 = gp.powmod(d,e,n)

print(c1)
print(c2)
print(n)

'''
145093797902822167319652632563913049204359441606914299371328132761737937841482985204772991693446558382687211295966125072432728114585260877882481917537185348909428560415929625399859565640798879751464916665858077652098718880371517761152276087514608872623033063875563356826449768135315600286686553435829384245134433664959750049696782982403767531350340684278871939622253835942508836597570164009480445326919831484001207931469848043961222999691304566605932331844481734994387604676780062351323993700832064016063406467090539944036593162781777831398673064877888159965880054730223661378027013210686762339031370347494499755842043157403690971225215004655175312643627502009620816754778588759723275253010895567475742391090669667988777717071600553719238830821999675630958162460547881544109850105236232159309537820403872727855391181941233211235876250798959167546860843659326405803024282470037020615626816534084522390299126332179146654832494

2761037910837718967061344195511979487994565044893561932920759186334785007440675894550166860632297873008400477594874122549824259651042906989018873497146326283220733850925963615819718647323108403061127797014213550645256691439295240651416176938533365428855831510041737319867214689836476665916037080648303266162609644824679782767672958160634270996992056182050815770464509352352622343572368757425935514622305972419508210848875697588255141320862169327664900990336717957506626667360479823775813415882223445888081908620554011130435520271237674956274080261300861326040405663427207665868898706364396527241733714445261200657405654370573827465006950534665688659874266680482613402133022739399689452087542656641275043233968350187385896117067102805499443547191573033143066075983801853574223210095894776380595919582689776780821295300553389588380527659421512397786402384504538653817177037906936827812894673284872232424415086422934862915801337

3287002712425388307525352609100624748000272472736874666500547841318591852594619595724087209914853196867692948250150501764076446154470673884523284309784517787183054246280337398098853243684127104584733672924352341481572093454807255602936733377039997650201840331363344239719297203152251916861311582291699460040753803661345073084832894779090488743449087119526126541942853573076715474894397009565884537900866295889520532273851131982999253534600891259155672158005086674638844910604020655531132043490450001206903667855774008230185435154887685054704162605627162865608268235359819470906793478144795375880249991003056592569994537140155966341660560671914544355445680021310815797523132967939090744815795215539133448449248304650191105105400480778072455609675366453408226825706923640521370456175259373003734277093133962318272307543941384223016249143554311711183964923672359210163040661231350422086972190979806820525109574548334715135305259
'''

分析：1.p与q都是随机的1024位的二进制数，这使得n会变得非常大，加之大正整数是很难分解的，所以这道

题并不是通过分解n来求解的。

2.e = 0x10001 十六进制转换为十进制及e=65537

3.n = pqq

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

观察发现n与phi有公因子q

4.c1 = gp.powmod(m,e,n) 即 m^e=k1pq*q+c1 *

c2 = gp.powmod(d,e,n) 即**d^e=k2pqq+c2

解题思路：

1.题目给出了一组c1,c2,n的值，泄露了d的信息，即d^e mod n。同时我们发现phi与n有公因子

q,n=pqq,phi=(p-1)(q-1)q。

2.(d^e mod n )*(e^e mod n) mod n= (de)^e mod n=(kphi+1)^e mod n。

3.那么我们现在的想法就是设法求出q,再将n分解为p,q，接着就可以通过逆元求解出d的值。

4.这样我们就知道c即c1,n,d的值，进而解出m，破译密文。

二、Hash

2.1 What is Hash

2.1.1 Hash and background:

Hash,一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过

散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空

间通常远小于输入的空间。它其实就是一个算法，最简单的算法就是加减乘除，比方，我设计个数字算

法，输入+7=输出，比如我输入1，输出为8；输入2，输出为9。

哈希算法不过是一个更为复杂的运算，它的输入可以是字符串，可以是数据，可以是任何文件，经过哈

希运算后，变成一个固定长度的输出，该输出就是哈希值。但是哈希算法有一个很大的特点，就是你不

能从结果推算出输入,所以又称为不可逆的算法。

安全，这是Hash的最大优点！

2.1.2 Hash’s advantages:

1.不可逆：在具备编码功能的同时，哈希算法也作为一种加密算法存在。即，你无法通过分析哈希值计

算出源文件的样子，换句话说：你不可能通过观察香肠的纹理推测出猪原来的样子。

2.计算极快：20G高清电影和一个5K文本文件复杂度相同，计算量都极小，可以在0.1秒内得出结果。也

就是说，不管猪有多肥，骨头多硬，做成香肠都只要眨眨眼的时间。

2.1.3 Applied fields:

哈希算法的不可逆特性使其在以下领域使用广泛

1.密码，我们日常使用的各种电子密码本质上都是基于hash的，你不用担心支付宝的工作人员会把你的

密码泄漏给第三方，因为你的登录密码是先经过 hash+各种复杂算法得出密文后 再存进支付宝的数据库

里的2.文件完整性校验，通过对文件进行hash，得出一段hash值 ，这样文件内容以后被修改了，hash值就

会变。 MD5 Hash算法的”数字指纹”特性，使它成为应用最广泛的一种文件完整性校验和(Checksum)算

法，不少Unix系统有提供计算md5 checksum的命令。

3.数字签名，数字签名技术是将摘要信息用发送者的私钥加密，与原文一起传送给接收者。接收者只有

用发送者的公钥才能解密被加密的摘要信息，然后用HASH函数对收到的原文产生一个摘要信息，与解

密的摘要信息对比。如果相同，则说明收到的信息是完整的，在传输过程中没有被修改，否则说明信息

被修改过，因此数字签名能够验证信息的完整性。

此外，hash算法在区块链领域也使用广泛。

2.2 Eg analyze(MD5 in Hash)

2.2.1 MD5

MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过一些列的处理后，

算法输出由四个32位分组组成的128位散列值。具体的步骤如下所示：

1、填充

如果输入信息的长度(bit)对512求余的结果不等于448，就需要填充使得对512求余结果等于448。填充

的方法是填充一个1和n个0。填充完成后，信息的长度为N*512+448

2、记录信息长度

用64位内存来存储填充前信息长度。这64位加在第一步结果的后面，这样信息长度就变为N512 + 448 +

*64 = (N+1)*512

3、装入标准的幻数（四个整数）

标准的幻数（物理顺序）是（A=(01234567)16，B=(89ABCDEF)16，C=(FEDCBA98)16，D=

(76543210)16）。如果在程序中定义应该是（A=0X67452301L，B=0XEFCDAB89L，

C=0X98BADCFEL，D=0X10325476L)。

2.2.2 Crypto–md5:

一个名为Hacker的人想给小彭加德育分，但是需要小彭的学号和寝室号才能完成加分。

Hacker自己只找到了学号和寝室号对应的md5值，聪明的你能帮助Hacker拿到学号和寝室号吗？

学号：71c5a9bd7cc3a8e563efe4171f07b427

寝室号：cb1592d95b7e3846451eab3728eeaa51

分析：

md5是一种信息摘要算法，不可反向解密，不同长度的内容加密后都是32位。它是单向密码体制，从明

文到密文的不可逆映射，只有加密过程没有解密过程，所以我们没法通过运算来解开密文得到明文。由

于md5是一种散列函数，运用Hash算法，在计算过程中原文会随机丢失，仅仅根据MD5的计算过程和

得到的最终结果，是无法逆向计算出明文的。

1.题目中的MD5密文并未加入盐作为干扰，都是标准的32位密文，解密时并没有非常困难，可以通过考

虑穷举法进行暴力求解。

2.通过迭代组合形成若干明文组，再将明文组进行utf-8编码成密文，然后与题目中的密文进行比较，当

两者一致时即“破译”成功，输出得到flag。

脚本如下：

1.引用hash

给定范围

运用for循环进行枚举

2.学号的格式为：19XXXXXXXX

我们发现已经给出部分明文，我们只需要解出剩下的8位明文即可，即设置8个变量

1
2
3
4
5
6
7
#coding: utf-8 

import hashlib 

dic = '0123456789' 

for i in range(1000):a,b,c,d,e,f,g

3.接着组成密文组t 

1
t ='19'+str(a)+str(b)+str(c)+str(d)+str(e)+str(f)+str(g)+str(h)

4.进行MD5算法，utf-8编码，所得密文与原密文比对，正确即输出，得到flag

1
2
3
4
5
md5 = hashlib.md5(t.encode('utf-8')).hexdigest() 

if md5[:32] == '71c5a9bd7cc3a8e563efe4171f07b427': 

print (t)

运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#coding: utf-8 

import hashlib 

dic = '0123456789' 

for i in range(1000): 
    for a in dic: 
        for b in dic: 
            for c in dic: 
                for d in dic: 
                    for e in dic:
                        for f in dic:
                            for g in dic: 
                                for h in dic: 
                                    t ='19'+str(a)+str(b)+str(c)+str(d)+str(e)+str(f)+str(g)+str(h) 
                                    md5 = hashlib.md5(t.encode('utf-8')).hexdigest() 
                                    if md5[:32] == '71c5a9bd7cc3a8e563efe4171f07b427': 
                                        print (t)
                                        break

求解完学号，寝室号的解密也是类似的：

注意到寝室号格式为：XX-XXXX

那么在组合时注意加入字符‘-’即可

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
#coding: utf-8import hashlib 

from tqdm import tqdm 

for i in tqdm(range(1000)): 

pass 

dic = '0123456789' 

for i in range(1000): 

        for a in dic: 

          for b in dic: 

            for c in dic: 

              for d in dic: 

                for e in dic: 

                  for f in dic: 

                                  t =str(a)+str(b)+'-'+str(c)+str(d)+str(e)+str(f) 

                                  md5 = hashlib.md5(t.encode('utf-8')).hexdigest() 

#print t 

if md5[:32] == 'cb1592d95b7e3846451eab3728eeaa51': 

print (t)

综上，flag为

SYC{1919114514,81-2048}

三、ECC

3.1 What is ECC

ECC与RSA一样都属于非对称加密算法，但是，与传统的基于大质数分解难题的加密算法不同，该加密方式基于 “离散对数” 这种数学难题。

椭圆曲线加密（Elliptic Curve Cryptography），ECC加密算法是一种公钥加密技术，以椭圆曲线理论为基础。利用有限域上椭圆曲线的点构成的Abel群离散对数难解性，实现加密、解密和数字签名。将椭圆曲线中的加法运算与离散对数中的模乘运算相对应，就可以建立基于椭圆曲线的对应密码体制。

这里我不了解什么是群，什么是圆锥曲线理论，所以去CSDN了一下。

3.1.1 关于群：

image-20221113004400313

3.1.2 EIgamal：

image-20221115230741013

image-20221113155335598

实例
密钥生成选取素数p=150001，本原元a=7，密钥113

p=150001
a=7
d=113
ad%p
66436L
y=ad%p
print y
66436

由公式可得公钥为y=66436

加密，明文为m=809,随机整数为k=1000

m=809
k=1000
c1=ak%p
c1
90429L
c2=m*yk%p
c2
15061L

得到密文为(c1,c2)=(90429,15061)

解密

根据公式m1=c2/c1y%p，但其中有模逆运算，不能直接计算，可以用扩展欧几里得算法,先求c1y的模逆

extended_gcd(c1**d%p,p)
(-69199L, 2147L)

我们所需要的是正数，所以加上p，-69199+p=80802

然后就可以

80802*c2%p
809L

正是刚开始的明文809

(https://blog.csdn.net/boksic/article/details/7014386)

3.1.3 椭圆曲线(Elliptic curve):

image-20221113162838863

image-20221113181212306

image-20221113181017150

(3条消息) 椭圆曲线入门详解_boksic的博客-CSDN博客_怎么求解椭圆曲线的全部解点

3.1.4 ECC and background:

我们知道，RSA算法的优势就是算法原理简单，可以很容易的构造。但是缺点也很明显，需要足够长的密钥长度来保证数据的安全性。

image-20221113001055302

而现在移动终端的数目在逐渐增多，越来越多的运算是在移动终端上进行的，而移动终端的计算能力有限，超级计算机的计算能力在不断增强。按照摩尔定律，计算机处理器的性能，每两年就会翻一番。

image-20221113001147500

这就必然导致了一个矛盾：

image-20221113001250810

由此，ECC加密算法应运而生。
引文链接：https://blog.csdn.net/xuanli4845/article/details/115907886

3.2 ECC’s advantages

ECC主要优势是可以使用更小的密钥并提供相当高等级的安全。ECC164位的密钥产生一个安全级，相当于RSA 1024位密钥提供的保密强度，而且计算量较小，处理速度更快，存储空间和传输带宽占用较少。目前我国居民二代身份证正在使用 256 位的椭圆曲线密码，虚拟货币比特币也选择ECC作为加密算法。对于ECC加密算法的优点，那就是性能上的提升，同样的密钥长度，基于ECC加密要比基于RSA安全很多。

总结来说就是ECC算法能在短时间内达到RSA的加密效果，同时ECC的密钥更短，存储效率高，通信效率高。

3.3 ECC’s principle

3.3.1 Define ECC:

在有限域Fp中定义一个椭圆曲线，常用y2=x3+ax+b

Fp中只有p个元素，p为素数
Fp中，a+b≡c (mod p)，a×b≡c (mod p)，a/b≡c (mod p)
4a^3+27b^2≠0　(mod p) a，b是小于p的非负整数
x，y属于0到p-1间的证书，曲线标记为Ep（a，b）
阶：椭圆曲线上一点P，存在正整数n，使得nP=O∞，则n为P的阶，若n不存在，则P是无限阶的，有限域上定义的椭圆曲线上所有点的阶都存在。

椭圆曲线难题

K=kG，其中K,G为Ep（a,b）上的点，k为小于n的整数，n是点G的阶，给定k和G，计算K容易，但是给定K和G，求k就很难了！

因此，设K为公钥，k为私钥，G为基点。

加密过程
A选定一条椭圆曲线Ep（a,b），并取曲线上一点作为基点G
A选择一个私钥k，并生成公钥K=kG
A将Ep（a,b）和k，G发送给B
B收到后将明文编码到Ep（a,b）上一点M，并产生一个随机数r
B计算点C1=M+rK，C2=rG
B将C1，C2传给A
A计算C1-kC2=M+rkG-krG=M
A对M解码得到明文
攻击者只能得到Ep（a,b），G，K，C1，C2，没有k就无法得到M。

签名验签流程
A选定一条椭圆曲线Ep（a，b），并取曲线上一点作为基点G
A选择一个私钥k，并生成公钥K=kG
A产生一个随机数r，计算R(x,y)=rG
A计算Hash=SHA(M)，M‘=M(modp)
A计算S=（Hash+M’k）/r(modp)
B获得S和M’，Ep(a,b)，K，R(x,y)
B计算Hash=SHA(M)，M’=M(modp)
B计算R’=（Hash*G+M’K）/S=(HashG+M’*kG)*r/(Hash+M’k)=rG=R（x,y），若R’=R，则验签成功。
https://blog.csdn.net/leo_wonty/article/details/7366418

3.3.2 Eg:

Eg1

image-20221114084747780

(3条消息) 椭圆曲线密码算术（ECC）原理_Soul fragments的博客-CSDN博客_ecc原理

(3条消息) ECC椭圆曲线加解密原理详解(配图)_NFTDigger的博客-CSDN博客_椭圆曲线加密算法原理

Eg2

image-20221114141027959

ECC椭圆曲线详解(有具体实例) - Kalafinaian - 博客园 (cnblogs.com)

3.4 Crypto–ECC

阿鲁为了保护自己的qq，使用椭圆曲线加密了自己的qq密码。
嘉然觉得这样并不安全，于是决定拿到阿鲁的qq密码证明此事。
发现阿鲁的QQ密码就是椭圆曲线的公钥坐标之和。
现已知椭圆曲线各参数：

a = 2546417962

b = 33279036350

p = 190540091407103

私钥: k = 3068869

G = (25040232765915, 122045618759262)

求公钥K(x, y)

flag是SYC{}包上x+y的sha256值

Analyze:

1.通过观察题目我们发现，已知椭圆曲线加密Ep(a,b)参数为

a = 2546417962

b = 33279036350

p = 190540091407103

私钥: k = 3068869

G = (25040232765915, 122045618759262)

需要求解的是公钥K(x,y)的横坐标与纵坐标之和的sha256的值

2.我们已知k与G，求解公钥K相对较简单。但是，如果知道G与K，反过来求解k就会变得很困难。阿鲁为了保护自己的qq，使用椭圆曲线加密了自己的qq密码，其QQ密码为公钥K(x,y)的横坐标与纵坐标之和，这么做显然是不够安全的，我们只需要解出公钥K就“破译”成功。

根据椭圆曲线上的点的加法运算

image-20221114151012914

我们就计算能得到公钥K，拿到flag

Solve process：

1.写入已知数据

1
2
3
4
5
6
7
8
Gx = 25040232765915
Gy = 122045618759262
a = 2546417962
b = 33279036350
p = 190540091407103
k = 3068869
x = Gx
y = Gy

2.分根据P、Q两点是否重合，进行分类

1
2
3
4
5
6
7
8
9
for i in range(k-1):
    #若P、Q两点重合
    if (x==Gx and y==Gy):
        inv = pow(2*Gy, p-2,p)   
        temp = (3*Gx*Gx+a)*inv%p 
        #若P、Q两点不重合
    else:
        inv = pow((x-Gx), p-2,p)
        temp = (y-Gy)*inv%p

3.再通过椭圆曲线上的加法运算算出公钥K

1
2
3
4
5
6
 xr = (temp*temp-Gx-x)%p
    yr = (temp*(x-xr)-y)%p
 #print(i,xr,yr)
    x = xr
    y = yr
print(x+y)

脚本如下：

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
#输入已知数据
Gx = 25040232765915
Gy = 122045618759262
a = 2546417962
b = 33279036350
p = 190540091407103
k = 3068869
x = Gx
y = Gy
for i in range(k-1):
    #分类计算K的值
    #若P、Q两点重合
    if (x==Gx and y==Gy):
        inv = pow(2*Gy, p-2,p)   #费马小定理(1/2/Gy)%p=(2Gy)^p-2 %p
        temp = (3*Gx*Gx+a)*inv%p 
        #若P、Q两点不重合
    else:
        inv = pow((x-Gx), p-2,p)
        temp = (y-Gy)*inv%p

    xr = (temp*temp-Gx-x)%p
    yr = (temp*(x-xr)-y)%p
 #print(i,xr,yr)
    x = xr
    y = yr
print(x+y)

image-20221114092916083

QQ:196301645356440

4.sha256

1
2
3
4
5
6
7
8
#Hash.sha256


import hashlib
hash=hashlib.sha256();
hash.update(bytes('196301645356440',encoding='utf-8'))
print(hash.hexdigest())

得到sha256后的值：a6c50a41e9ff4678ff94a17e893f434952a32b2e70c78dfb726c4d78b4303471

image-20221114093108426

所以，flag为

SYC{a6c50a41e9ff4678ff94a17e893f434952a32b2e70c78dfb726c4d78b4303471}

四、Coppersmith&Lattice-based Cryptography

4.1 Define

4.1.1 Coppersmith：

Coppersmith定理攻击，也是针对n

Coppersmith定理指出在一个e阶的mod n多项式f(x)中，如果有一个根小于n^1/e，就可以运用一个O(log n)的算法求出这些根。

这个定理可以应用于rsa算法。如果e = 3并且在明文当中只有三分之二的比特是已知的，这种算法可以求出明文中所有的比特。

image-20221115094724598

4.1.2 Lattice-based Cryptography：

Background：

随着当下量子计算机的研制的迅速进展，量子算法亦是相应得以巨大突破。在量子计算模型下，经典数论假设的密码体系（如大整数分解，计算有限域/椭圆曲线上的离散对数问题等），存在多项式时间（PPT）的量子算法，换而言之，经典数论密码体系受到了极大的冲击，将有可能成为旧时代的眼泪。因此，能够抵抗量子计算机攻击的密码——“后量子”或“抗量子”密码便应运而生。

目前, 用于构建后量子密码系统的常见数学技巧包括：
1.杂凑函数,多变量方程(在构造签名方案时较有优势)
2.纠错码(更合适构造加密方案)
3.格(最通用的一类, 几乎所有经典密码概念都可以在格密码中实现)
4.超奇异椭圆曲线同源问题(当下较新的一类, 目前其中较受关注的有密钥交换和签名方案的构造,计算效率很低,还达不到实用性的要求)

image-20221115223034239

(3条消息) 格密码学习笔记（一）_中科院大学网安学院五班的博客-CSDN博客_格密码

4.2 Crypto–Lattice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import * 
import gmpy2 as gp 
from secret import flag 

m = bytes_to_long(flag) 

p = getPrime(1024) 
q = gp.next_prime(p^getPrime(300)) 

n = p*q*q  
e = 65537 

c = gp.powmod(m,e,n) 

print('n =',n) 
print('c =',c) 

'''
n = 1657441819757560493500517852783955669448453505565270030410061904903034812851838667903292681076179721746140392331192685190606078940084193957290326586494942522658447994684113206242147782786486488436062862050720479488907160079456425398688762594497865325047151851509869420955094484022711893914207287322595902861633185849920399826569309062936190162679696321445993297117512458125412547050580265204485812236589358129086671672828599162645076611983958397948578920439799452386250795654988454192963915928293305164506837479627943346663261467474305586884553923408358862832788883664773346582688933735310806488603282226770159631772761229230574671474094221451870770630961493950451576998259008044822492004077759659701132437773984472438535462757118722089434990869144816129748753152891554265248737014747786223673274064575777197461593456413962892395208072539632132385626016349698916261814365453919077654267526533803349663404621106450916027162399
c = 1593553679265125861785993192995912696703111560484695970440496248832386885660325028592530874649060028886120763183422597047360806209458935841437245811877714862968196063554261763749466409879047920508168205393706964912523940426199563334512062879052144213846731434858189341622618689853479805825788008893681015249513342688073719536077558806766432484683211750233531164855481666588757851308926988995968945742356896847523781439112333434449743267160262042077831263329769226240475721901216575639399568420398732862655239671453285258560223566086632412820111497447791858015410203252987331230298565756895805839776628672153301485185711776486346696438675451218026201460790552063913385567753045113924570385856031061350493346154777923602808727275442959100197205924675240921131973487280067779126475375849306092292239336121622197137677170815075931160633100612695431123755384954524364124384771024043229892682507314656508989478323824687786447911936
'''

五、Discrete Log

5.1 What is Discrete Log

离散对数被誉为当代密码学领域的三大基础之一。1976年，Diffifie和Hellman提出了一种密钥协商协议， 产生了首个离散对数系统模型；8年后，ElGamal提出了基于离散对数系统的公钥加密和签名方法，并奠定了离散对数密码学基础。从那时起，围绕离散对数系统产生了不少研究成果，本文阐述离散对数的基本概念，然后介绍基于离散对数的ElGamal的公钥加密方法和数字签名方法（DSA）。

5.1.1 Define Discrete Log:

image-20221115163033136

image-20221115163111394

定义

当模 m有原根时，设 a为模 m的一个原根，则当
$$
ak≡x(mod m)时： Indx≡k(mod ϕ(m))
$$
，此处的 Indx为 x以整数 a为底，模 ϕ(m)时的离散对数值.

性质

离散对数和一般的对数有着相类似的性质：

image-20221115161637062

示例

对模5，ϕ(5)=5−1=4.有个原根是2. 因为

image-20221115161703314

离散对数概念 - 瀚海星空 - 周海汉博客 (abloz.com)

5.2 Crypto–Discrete Log

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
import gmpy2 as gp 
from Crypto.Util.number import * 
from Crypto.Cipher import AES  
import random 

from secret import flag,key 

def ts(g,p):
    return gp.powmod(g,(p-1)//2,p) == 1 

    
class ELG():
    def __init__(self,m):
        self.m = m  


    def creation(self):
        global p,g 
        
        
        while True:
            p = 2  
            pr = [] 
            for i in range(10): 
                a = getPrime(20)
                pr.append(a) 
                p *= a**random.randint(1,4) 
            if isPrime(p+1):
                break   
        p += 1  
        print('p =',p) 
        print('pr =',pr) 
        g = 2
        while True :
            g+=1 
            if ts(g,p):
                break 
        print('g =',g) 
        priv_a = random.randint(1,p-1) 
        pub_A = gp.powmod(g,priv_a,p) 
        
        
        print('pub =',pub_A) 
        return priv_a,pub_A 
        
    
    def enc(self,m,pub):
        k = random.randint(2<<100,2<<200)  
        c1 = gp.powmod(g,k,p) 
        c2 = (m * gp.powmod(pub,k,p)) % p 
        return c1,c2  

    def conn(self): 
        priv,pub = self.creation() 
        c1,c2 = self.enc(self.m,pub) 
        return c1,c2 
       

DEBUG = True 
if DEBUG: 
    aes = AES.new(key,AES.MODE_ECB)  
    elg = ELG(bytes_to_long(flag)) 
    c1,c2 = elg.conn() 
    print('c1 =',c1) 
    print('c2 =',c2) 
    c = aes.encrypt(flag)  
    print('cipher =',bytes_to_long(c))    

'''
p = 240311898144666004845993472603553263322756300779157768701176199291766409589743098329948576886913307536581636947347700640539029536089210573230307671485961868117315471159814486642321020898269103855126517533262247331484819745914498053780059371263306840883425781625061104966618125509054939865409539648498696187295927
g = 5
pub = 134285622222383211593143419284735141120812420703242474727692334574646766372588113350683719458438557808968651014501757534179743215386357063432496866596113430845534517856556614675236061221959886358825348089193378086912994104626194570995572907279789332330634572963965215940753665380396874414753113588963071439984133
c1 = 59866977306496443433230989875501170590733738724206572571973692325202707443627775293269002455283846854135556345025196628657530983549383681055008873942332984996831735632074040992205674787686019847478343708531796808561868062324972209667292857694231350874772127330748101130540816455846043028497370515427917876173767
c2 = 189736523869687408218680256920128645519881608991064724826055201457101208294761171595467115162913230133265415706153044192480307701067740580637047863932982867754412493322841249939735690673297501484346546496379585941155099078148120702397606052034259931372433234626469922863663420459070532806854867523903923301588710

cipher = 106965036567008443490243813427422441161051668015352122219256553139516361341928
'''

六、Inverse

6.1 What is inverse

6.6.1 Define inverse:

Inverse，即逆元。

我们都知道倒数的概念，逆元可以说是扩大了概念的倒数。在模运算中，若ab≡1（mod m)，则称b为模m下a的逆元。

求解公式(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：

6.1.2 Inverse’s application：

那么逆元有什么用呢？
(a + b) % p = (a%p + b%p) %p （对）
(a - b) % p = (a%p - b%p) %p （对）
(a * b) % p = (a%p * b%p) %p （对）
(a / b) % p = (a%p / b%p) %p （错）
在求余的过程中我们发现只有除法是不能分开运算的，而当a过大时，在计算除法过程中可能会造成比较大的精度损失，所以对于这种情况我们一般会把式子转换成那么(a / b) % p = (a * inv(b) ) % p = (a % p * inv(b) % p) % p来进行计算。这样就解决了除法不能分开计算的问题。
需要注意只有a和p互质，a才有关于p的逆元

https://blog.csdn.net/weixin_45757507/article/details/107506285

6.1.3 Achieve ways：

1.费马小定理

费马小定理：(3条消息) 费马小定理及其应用_不见月光见星光的博客-CSDN博客_费马小定理应用

费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出。

如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）
费马小定理规定了p一定为一个质数，所以a和p一定互质
那么双方在modp的意义下同时除a可得
a^(p-2) ≡1/a (mod p)
也就是a^(p-2) ≡ inv(a) (mod p)
所以inv(a) = a^(p-2) (mod p)

2.扩展欧几里得算法求逆元

欧几里得算法：(3条消息) 欧几里得算法原理_ltrbless的博客-CSDN博客_欧几里得算法

如果gcd（a，p）=1；
那么就有ax+py=1
双方同时modp
就有ax≡1（modp）
因为py是p的倍数全部约掉了
此时x就是a的逆元
所以只需解出该情况下的扩展欧几里得方程的解问题就解决了

6.2 Inverse–Coding

参考书目以及参考的资料：

《An Introduction to Mathematical Cryptography》

(3条消息) Python在GF(2⁸)有限域上求解多项式的乘法逆元——基于扩展欧几里得算法_海绵菌的博客-CSDN博客_有限域多项式乘法

  • Title: Summary
  • Author: jrl
  • Created at: 2023-06-18 16:43:53
  • Updated at: 2023-07-26 18:40:30
  • Link: https://jrl777.github.io/2023/06/18/Summary/
  • License: This work is licensed under CC BY-NC-SA 4.0.
 Comments
On this page
Summary
  1. 一 、RSA
    1. 1.1 What is RSA
      1. 1.1.1 Define RSA：
      2. 1.1.2 Basic principle：
      3. 1.1.3 Summariz：
    2. 1.2 Tools and third-party libaries
      1. 1.2.1 RSA-tool :
      2. 1.2.2 Python :
    3. 1.3 Eg analyze
      1. 1.3.1 Easy RSA:
      2. 1.3.2 Crypto–RSA:
  2. 二、Hash
    1. 2.1 What is Hash
      1. 2.1.1 Hash and background:
      2. 2.1.2 Hash’s advantages:
      3. 2.1.3 Applied fields:
    2. 2.2 Eg analyze(MD5 in Hash)
      1. 2.2.1 MD5
      2. 2.2.2 Crypto–md5:
  3. 三、ECC
    1. 3.1 What is ECC
      1. 3.1.1 关于群：
      2. 3.1.2 EIgamal：
      3. 3.1.3 椭圆曲线(Elliptic curve):
      4. 3.1.4 ECC and background:
    2. 3.2 ECC’s advantages
    3. 3.3 ECC’s principle
      1. 3.3.1 Define ECC:
      2. 3.3.2 Eg:
    4. 3.4 Crypto–ECC
      1. Analyze:
      2. Solve process：
  4. 四、Coppersmith&Lattice-based Cryptography
    1. 4.1 Define
      1. 4.1.1 Coppersmith：
      2. 4.1.2 Lattice-based Cryptography：
    2. 4.2 Crypto–Lattice
  5. 五、Discrete Log
    1. 5.1 What is Discrete Log
      1. 5.1.1 Define Discrete Log:
    2. 5.2 Crypto–Discrete Log
  6. 六、Inverse
    1. 6.1 What is inverse
      1. 6.6.1 Define inverse:
      2. 6.1.2 Inverse’s application：
      3. 6.1.3 Achieve ways：
    2. 6.2 Inverse–Coding