search

RSA 介绍

RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。

RSA 算法的可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今，只有短的 RSA 密钥才可能被强力方式解破。到 2017 年为止，还没有任何可靠的攻击 RSA 算法的方式。

hashtag
基本原理

hashtag
公钥与私钥的产生

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

  2. 根据欧拉函数，求得 $\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$

  3. 选择一个小于 $\varphi (N)$ 的整数 $e$，使 $e$ 和 $\varphi (N)$ 互质。并求得 $e$ 关于 $\varphi (N)$ 的模反元素，命名为 $d$，有 $ed\equiv 1 \pmod {\varphi (N)}$

  4. 将 $p​$ 和 $q​$ 的记录销毁

此时，$(N,e)$ 是公钥，$(N,d)$ 是私钥。

hashtag
消息加密

首先需要将消息 以一个双方约定好的格式转化为一个小于 $N$，且与 $N$ 互质的整数 $m$。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：

me≡c(modN)m^{e}\equiv c\pmod N

hashtag
消息解密

利用密钥 $d​$ 进行解密。

cd≡m(modN)c^{d}\equiv m\pmod N

hashtag
正确性证明

即我们要证$m^{ed} \equiv m \bmod N$，已知$ed \equiv 1 \bmod \phi(N)$，那么 $ed=k\phi(N)+1$，即需要证明

mkϕ(N)+1≡m mod Nm^{k\phi(N)+1} \equiv m \bmod N

这里我们分两种情况证明

第一种情况 $gcd(m,N)=1​$，那么 $m^{\phi(N)} \equiv 1 \bmod N​$，因此原式成立。

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

m=xpm=xp

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

mϕ(q)≡1 mod qm^{\phi(q)} \equiv 1 \bmod q

进而

mkϕ(N)=mk(p−1)(q−1)=(mϕ(q))k(p−1)≡1 mod qm^{k\phi(N)}=m^{k(p-1)(q-1)}=(m^{\phi(q)})^{k(p-1)} \equiv 1 \bmod q

那么

mkϕ(N)+1=m+uqmm^{k\phi(N)+1}=m+uqm

进而

mkϕ(N)+1=m+uqxp=m+uxNm^{k\phi(N)+1}=m+uqxp=m+uxN

所以原式成立。

hashtag
基本工具

hashtag
RSAtool

  • 安装

  • 生成私钥

hashtag
RSA Converter

  • 根据给定密钥对，生成 pem 文件

  • 根据 $n$，$e$，$d$ 得出 $p$，$q$

hashtag
openssl

  • 查看公钥文件

  • 解密

更加具体的细节请参考 openssl --help。

hashtag
分解整数工具

hashtag
python 库

hashtag
primefac

整数分解库，包含了很多整数分解的算法。

hashtag
gmpy

  • gmpy.root(a, b)，返回一个元组 (x, y)，其中 x 为 a 开 b 次方的值，y 是判断 x 是否为整数的布尔型变量

hashtag
gmpy2

安装时，可能会需要自己另行安装 mpfr 与 mpc 库。

  • gmpy2.iroot(a, b)，类似于 gmpy.root(a,b)

hashtag
pycrypto

  • 安装

  • 使用

hashtag
Jarvis OJ - Basic - veryeasyRSA

p = 3487583947589437589237958723892346254777 q = 8767867843568934765983476584376578389

e = 65537

求 d =

请提交 PCTF{d}

直接根据 $ed\equiv 1 \pmod{\varphi (N)}$，其中 $\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$，可得 $d$。

hashtag
2018 CodeGate CTF Rsababy

程序就是一个简单的 RSA，不过程序还生成了两个奇怪的数

所以，问题应该出自这里，所以我们就从此下手，不放这里先假设 const = 0xdeadbeef。那么

eg=ed∗(p−const)eg = ed * (p-const)

进而，根据 RSA 可知

2eg=2ed∗(p−const)=2p−const(modn)2^{eg}=2^{ed * (p-const)}=2^{p-const} \pmod n
2p−const∗2const−1=2p−1(modn)2^{p-const} * 2^{const-1} = 2^{p-1} \pmod n

所以

2p−1=2eg∗2const−1+kn2^{p-1} = 2^{eg} * 2^{const-1}+kn

而与此同时根据费马小定理，我们知道

2p−1≡1(modp)2^{p-1} \equiv 1 \pmod p

所以

p∣2p−1−1∣2eg+const−1−1+knp|2^{p-1}-1 | 2^{eg+const-1}-1+kn

进而

p∣2eg+const−1−1p|2^{eg+const-1}-1

所以

p∣gcd(2eg+const−1−1,n)p|gcd(2^{eg+const-1}-1,n)

因此，代码如下

hashtag
2018 国家安全周 pure math

题目的基本描述是这个样子的

我们的目的基本上就是求得 FLAG，那么怎么做呢?这个题目需要我们具有较好的数论功底。

根据题目中这样的内容，我们可以假设 $p$，$q$ 都是大素数，那么

$p^{q-1} \equiv 1\bmod q$

那么

$p^{q} \equiv p \bmod pq$

那么我们可以根据 3）知道

$p^q+q^p \equiv p+q \bmod pq$

而 $p+q$ 又显然小于 $pq$，所以我们就知道 $p+q$ 的数值。

进一步，我们假设1），2），3），4），5）对应的值分别为 $x_1$, $x_2$, $x_3$, $x_4$, $x_5$ 则

根据4），我们可以知道

$(p+q)^{p+q} \equiv p^{p+q}+q^{p+q} \bmod pq$

又因为1）和 2），则

$p^pp \equiv px_1\bmod pq$

$q^qq \equiv qx_2 \bmod pq$

因此

$px_1+qx_2 \equiv x_4 \bmod pq$

根据 $x_1$ 和 $x_2$ 的求得方式，我们可以知道这里也是等号，因此我们得到了一个二元一次方程组，直接求解即可。

flag 如下

hashtag
2018 Pwnhub LHY

首先分析这段代码

由于 gmpy.is_prime 要么返回1，要么返回 0，所以我们可以很容易地试出来 y 是素数，x+1 也是素数，并且

$(x^2-1)^2\equiv 0 \bmod (2xy-1)$

为了式子能够整除，猜测 $x=2y$ 。

于是，对于下面的内容

$p$ 和 $q$ 自然为

$p=next_prime(9y^3)$

$q=next_prime(6y^3)$

根据素数的间隔，可以知道 $p$ 和 $q$ 最多比括号里的数字大一点，这里一般不会超过 $1000$。

那么

$n \geq 54y^6$

所以我们知道了 $y$ 的上界，而对于 $y$ 的下界其实也不会离上界太远，我们大概减个几十万。进而，我们利用二分查找的方式来寻找 $p$ 和 $q$，如下

PreviousRSA 侧信道攻击Nextd_attacks

Last updated