MENU

RSA学习笔记

November 12, 2020 • Read: 474 • CTF阅读设置

概述

通信技术是为了实现信息的传输,但为了实现信息传输的安全性,则需要对信息进行加密。$RSA$就是当下的主流加密方式。

凯撒密码是一种对称加密,加密解密使用了同种规则,即明文+密钥->密文 密文-密钥->明文 。在整个过程中传输的密钥是不变的,通信双方都需要知道密钥,这就会增大了传输过程中密钥泄露的风险。而$RSA$是一种非对称加密 加密解密采用了不同规则,即 明文+公钥->密文 密文+私钥->明文。公钥是公开的,而私钥则只要保留在信息的接受者手中,这就一定程度保证了信息传输的安全性。

加密解密原理

$$ 加密 \qquad c\equiv m^e \mod n \\ 解密 \qquad m\equiv c^d \mod n $$

其中$m$为明文 $c$为密文

给定公钥$KU (e,n)$ 实现加密 给定私钥$KR (d,n)$ 实现解密

加密过程

1.寻找两个不等的质数$p,q$

2.$n=pq$

3.欧拉函数$\phi(n)=(p-1)(q-1)$ 表示少于或等于n的数中与n互质的数的数目

4.确定e $1<e<\phi(n) $ $e与\phi(n)$互质 即$gcd(e,\phi(n)=1$

5.确定d $de \mod \phi(n)=1$ 即 $de=k\phi(n)+1,k\ge1$

简单分析

整个加密过程的安全性在于 找到两个很大的质数相乘得到的一个数很容易,但要将一个很大的数分解为两个质数则基本不可能实现。至少在量子计算机出现之前,2048位的$RSA$加密极其安全。

参考链接

http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

https://xz.aliyun.com/t/2446#toc-5

分解n

在线分解
http://factordb.com
yafu分解

yafu​下载地址 https://sourceforge.net/projects/yafu/

启动yafu-x64.exe键入factor($n),结果将保存在factor.log文件中

或者cd到根目录下,执行

yafu-x64.exe factor($n)

其中$n$为模数。

yafu分解从文件读取,将n置于1.txt中,注意最后需要换行

yafu-x64 "factor(@)" -batchfile 1.txt
Last Modified: November 9, 2021