大致了解一下RSA以及出题套路

前言

最近做的CTF题目遇到RSA加密总是不会,于是参考资料学习一番,小结自己的学习过程,怕自己某天又忘记了
RSA是属于现代密码学的范畴,现代密码学的终极目标是:发明永远无法破解的加密算法
而他们很多又是跟二进制相关,二进制加密的唯一算法 XOR
下面两个标准就很典型。。。
DES 数据加密标准
AES 高级加密标准
对于上面的东西一知半解。。什么轮子函数都没了解清楚,还有一些什么盒子之类的东西。。。emmm以后在深究吧

正文

跟标题一样,我只是简单了解RSA算法,然后把自己得理解写出来,毕竟那些什么欧拉公式,什么高斯的数论,看也看一到两天,太费时间。。。

RSA是一种非对称加密算法,它由 公钥(n/e),私钥(n/d),明文M和密文C组成。

RSA的大致过程

CgsFCF.md.png

选取两个大素数生成n,p和q,n=p*q,这里的n目前大都是在1024位左右,难以破解,因为它越长,分解起来就越难
随机选取加密密钥e,保证e和(p-1)(q-1)互素

计算解密私钥 e*d ≡ 1 mod (p-1)(q-1)

加密 c=m^e mod n

解密

1
m=c^d mod n

这里的c指的是密文,m指的是明文
其中(n,e)为公钥,(n,d)为私钥

介绍一个同余运算的概念

两个整数a,b,它们除以整数M所得的余数相等:a ≡ b(mod m),比如说5除3余数为2,11除3余数也为2,于是可写成11 ≡ 5(mod 3)

然后就做了几个题目,发现嫌他们的套路就是不停的玩转这几个参数。。。。

1
2
3
4
已知p、q、e求d
已知p、q、e和密文 求明文
已知n、e和密文 求明文
已知公钥和密文 求明文

还有就是简单记录一下相关工具的用法

RSAtool

这个还是比较方便的,但还是觉得脚本顺手
Cgsk34.md.png

Keysize(Bits):填写你N的位数
Public Exp.(E):填写你的e的十进制值
Number Base:填写你下面N的进制(一般采用10进制)
Modulus(N):填写N的十进制数(和Number Base填写的要对应)
然后点击左下角的Factor N
就会自动分解出P和Q
然后点击左下角的Calc. D
就会自动计算出D
然后点击左下角的Test
(这里好像有个Bug,要先加密一次,才能用解密功能)
然后把你的密文放在result里,点击decrypto
即可得到解密后的答案

yafu

一个大数分解工具
用命令行进入打此目录下,命令如下,N是你输入的大数
yafu-x64.exe factor(N)
CgsZuR.md.png

还有一个PARI。。。这好像也是一种语言。。一般是用来将大数16进制转10进制。。或者是判断N的位数使用
CgsHq1.md.png
反正不理了,指令也很简单:
第一步:输入数字
(当然,如果输入16进制,你要带上0x,他会底下自动给你显示10进制,十分方便)
第二步: binary(x)
他就会帮你把这个大数分解成2进制
第三步: length(x)
他可以帮你输出这个N的位数

openssl

有时候遇到下面这种格式的,就会选择用openssl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
-----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAQEDZxmNa1YU6VgTrdjyKkcX
vHK+HqvZM9G4aUT9t1uO0jC+YtfRtp0iIJXBKMhvggEuyxFhkf2dAYptAvhNsnvF
GiEwfchvS/dxxpHBQ+Wr5Um1vS1usaIf1icOfhtI/gYR+7LhsLNSTm9N6LTko0Xa
RKE96CW3JgjbbHxKQLeCZubIe7/e9rSDgdScRQeli81Ht21ktFkIsVi9frxNrLCx
z9bCwZV09A6y79Dp4Q3HAFytObyvUrnqw4czaNaQMcXnJGhKRPBo79HT3Altm11k
EeWL3uQ+RrmaDQSUudsoGVr5Aa/xMNSm4gPa0I2lf6fkAmKlutsqMj7aKLRGlqsw
XQKCAQEA85Wdl44C658G3vPzNdj4r9dgmVHdrGC3FLbCKvD6kS8hCzQga9JKlgHH
jfSgJ18Qf9OrVS2VBX65NOcb3c1wRcJLGFh7jI/PWt1MXYPwx3yU3JxQy+Q44rZ7
r9MWM7aq8XgdkMOtbwPQN7MyGAGyNUbUg+Z+JgZ/eyI0fdvAwtWSzoFMv138zBQU
N/FOCzmQ+IBh5fC65fAeP6cNsOlgXnz9V16cge/uxSnDP9kDeiD9is1ROsljd2gx
PmP5g4rjURzdCporUW8hSMjUdaNgoGNZRJc57s0lGrtCsBRXPkOfL6RXNVeyVpn/
wR5jHOjul1qG5+JyvPX3apNFA0j+Pw==
-----END PUBLIC KEY-----

9dsjJA.png

1
openssl rsa -in public.key -pubin -noout -text -modulus

上面的public.key就是你所需要查看的文件名

然后使用密钥文件进行解密的话

1
openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag.dec

flag.enc是加密文件 private.pem是密钥 flag.dec解密文件

配合下面的Python脚本在linux下使用,记得在同一文件夹下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import math
import sys
from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)

keypair.p = 258631601377848992211685134376492365269
keypair.q = 286924040788547268861394901519826758027
keypair.e = 65537

keypair.n = keypair.p * keypair.q
Qn = long((keypair.p-1) * (keypair.q-1))

i = 1
while (True):
x = (Qn * i ) + 1
if (x % keypair.e == 0):
keypair.d = x / keypair.e
break
i += 1

private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()

记得修改一下p q e

参考文章:
http://www.freebuf.com/column/148185.html
http://skysec.top/2017/07/25/RSA常用工具/


听说,打赏我的人最后都成了大佬。



文章目录
  1. 1. 前言
  2. 2. 正文
    1. 2.1. RSA的大致过程
    2. 2.2. 介绍一个同余运算的概念
    3. 2.3. 还有就是简单记录一下相关工具的用法
      1. 2.3.1. RSAtool
      2. 2.3.2. yafu
      3. 2.3.3. openssl