RSA两种特殊攻击情况

P和q的不当分解

|p-q|很大时，一定存在某个参数ip较小，这里我们假设p较小我们可以通过穷举法分解模数，但是很少遇到

• 如果两个质数差距很小（即 q - p 很小），那么：

  1	n = p * q = (a - b)(a + b) = a^2 - b^2

  推导过程如下：

  • 令：a = (p + q) / 2，b = (q - p) / 2
  • 则：n = a^2 - b^2
  • 所以我们可以从 a = ⌈√n⌉ 开始，不断尝试 b^2 = a^2 - n 是否是完全平方数
  • 如果找到了某个 a 使得 b^2 = a^2 - n 是完全平方数，就能还原 p = a - b, q = a + b

举例

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

import gmpy2
from Crypto.Util.number import getPrime
import random

# 生成 p 和 q
p = getPrime(1024)
q = gmpy2.next_prime(p, p + 10000) #这个数的下一个素数在某个范围内。
n = p * q

print("p=",p)
print("q=",q)
print("n=",n)
def factor(n):
    a = gmpy2.iroot(n, 2)[0] #a可以看作p+q
    while True:
        a+=1
        b2 = a * a - n  #

        if gmpy2.is_square(b2):#判断b2是否是全平方
            b2 = gmpy2.mpz(b2)  # 转换为大整数
            b, xflag = gmpy2.iroot(b2, 2) #返回元组
            assert xflag  # 如果能平方返回True
            return (a - b, a + b)

print(factor(n))

一个变式题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

from Crypto.Util.number import *
import gmpy2
from flag import flag
assert flag[:5]==b'flag{'
​
m1 = bytes_to_long(flag[:20])
p  = getPrime(512)
p1 = gmpy2.next_prime(p)
q  = getPrime(512)
q1 = gmpy2.next_prime(q)
n1 = p*q*p1*q1
print('n1 =',n1)
e = 0x10001
c1 = pow(m1,e,n1)
print('c1 =',c1)
​

这里有n=四个素数因子乘积

极客大挑战2024中国剩余定理复现

CRT(中国剩余定理)

一些定理的证明

1.证明辗转相除法

a=bq+r

证明gcd(a,b)=gcd(b,r)

已知gcd(a,b)|a,gcd(a,b)|b

r=a-bq,--->gcd(a,b)|r

所有gcd(a,b)<=gcd(b,r)

gcd(b,r)|b,gcd(b,r)|r并且gcd(b,r)|a

所以gcd(b,c)<=gcd(a,b)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def gcd(a,b):
    while b!=0:
        r=a%b
        a=b
        b=r
    return a
print("请输入a")
a=int(input())
print("请输入b")
b=int(input())
print(gcd(a,b))
n=2
while n!=0:
    n=n-1
    print(n)

2. 证明裴蜀定理

如果a和b是不为0的整数，则有整数x,y，是的ax+by=gcd(a,b)

gcd(a,b)=gcd(b,a%b=r1)=gcd(r1,b%r1=r2)=gcd(r2,r1%r2=r3)=gcd(r3,r2%r3=0),,r3为最大公约数

r3=r1-?r2,=r1-(b-?r1)=?r1+?b=?(a-b?)+?b=?a+?b(?为任意整数)

推论：

a,b互质<-->ax+by=1(a,b不全为0)

如果a和b是不全为0的整数，并且ax+by=c有解，那么c一定是gcd(a,b)的整数倍

a和b两项的裴蜀定理可以推广到多项（ax+by+cz=gcd(a,b,c)

AES加密回顾以及代码实现

Rijndael_Animation_v4_eng-html5

这里放了一个动态演示AES加密过程的网站，有兴趣的可以观看，建议挂代理食用

Rcon是轮常量：

前言

接触密码学也两个月了，之前是学过AES的但是都是简单看了下大概，打CTF的时候喜欢python库脚本一把梭，对AES涉及的一些数学原理不理解，希望尝试用python实现AES加密。

重要的前置知识，有限域多项式乘法运算。

1.GF(2⁸)中的多项式

伽罗瓦域之前以及了解过，大家有兴趣可以自己搜一下

DH 密钥交换协议

在基于对称加密进行安全通信的过程中，通信双方需要持有一个共享的密钥。只有这样，由任何一方加密的信息才能由另一方使用相同的密钥解密。但是在能够安全的通信之前，通信双方应该如何约定一个共享的密钥呢？这就是安全中的经典问题：密钥配送问题（Key Distribution Problem[1]）。

Diffe-Hellman密钥交换协议只是其中一种约定功能共享密钥的方式，

DHKE协议简介

DHKE是一种通过公共通道安全地交换加密密钥的数学方法，以Whitfield Diffie和Martin Hellman的名字命名。

数学原理

$c=G^e mod P(0<=c<P)$

G是P的原根，满足条件

{g1modp,g2modp,g3modp,…,gp−1modp}={1,2,3,…,p−1}

DHKE协议的过程

LLL算法

1. 简介：LLL算法用于解决最短向量问题的多项式时间复杂度算法。

LLL算法解释

对格的认识

不同的基也可以生成同一个格。

例如一个基向量是（1,0)和（0，1）构成的格。该格用数学符号表示。

伪随机数生成器(PRNG)

前言

随机数生成分为伪随机，真随机。真随机是利用现实中的电子元件噪音来生产的。

伪随机数：用真随机数生成种子，用伪随机数生成器生成伪随机数位流

PRNG算法大致分为两类：

• 专用算法：为生成伪随机位流而专门设计。

• 基于现有密码算法的算法：密码算法会随机化输入数据。

  • 对称分组密码、
  • 哈希函数
  • 消息验证码

专用算法

LCG(线性同余生成器)

$x_{n+1}=(aX_n+b)mod m$

MD5算法

MD5（单向散列算法） 的全称是Message-Digest Algorithm 5（信息-摘要算法）

MD5的功能:

输入任意长度的信息，经过处理，输出位128位的信息；不同的输入可以得到不同的结果(唯一性)

根据128位输出结果反推出输入信息是及其困难的(不可逆)

• 散列函数

散列函数是一种将输入数据映射到固定大小的散列值的函数。它通过对输入数据进行计算，生成一个唯一的散列值，用于快速查找或验证数据的完整性。

散列函数的特点和要求

1. 均匀分布:散列函数将输入数据均匀地分布在散列值的范围内，以避免碰撞(即多个不同的数据得到相同散列值)的发生--不过无法完全避免
2. 碰撞概率最小化

• memcpy

Weil paIring

• 前言

编者对群的了解比较基础，可能一些证明不太会

借鉴crypt03-15.tex.dvi

双线性映射

• 在数学中，一个双线性映射是由两个向量空间上的元素，生成第三个向量空间上一个元素之函数，并且该函数对每个参数都是线性的。例如矩阵乘法就是一个例子。

• 线性性

x,x'∈V,y'∈W,以及标量a,b为整数，双线性映射$f:V×W→K$

必须满足:

$f(ax+bx',y)=af(x,y)+bf(x',y)$ $f(x,ay+by')=af(x,y)+bf(x,y')$