【密码学】AES简单学习

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

欧拉函数

公式

φ(n)=(p-1)(q-1)

小于x并且和x互质的数的个数

相关概念

因数：a*b=c 那么就称 a、b 是 c 的因数

素数：一个数如果除了1与它本身之外没有其他的因数，那么这个数就被称为素数（prime）

公因数：共同的因数，比如 8 和 10 的公因数是 2、1，最大公因数是 2

互质：最大公因数是 1

例如：7、3，最大公因数是 1，他们互质 gcb(7,3)=1

φ(10)=4 (1,3,7,9)

对于公式的解释

p、q 都是素数，例如：10，p、q 分别为 2、5，φ(10)=(p-1)(q-1)=(2-1)(5-1)=4

取模运算

如果存在正整数 m 与两个整数 a、b，如果 a-b 能被 m 整除，那么 a 和 b 模 m 同余

记作：a ≡ b mod(m)

模指数运算

先进行指数运算，在进行取模运算

记作：a ≡ bⁿ mod(m)

python中处理函数

pow(x,y,z) 意思是计算x的y次方，如果z存在对结果进行取模等效于pow(x,y)%z

欧几里得拓展算法

对于不完全为0的非负整数a,b，gcb(a,b)表示a，b的最大公约数，必然存在x，y使得gcb(a,b)=ax+by

证明：
假设 a>b
1、显然当 b=0，gcd（a，b）=a，此时 x=1，y=0；
2、ab!=0 时，设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

RSA涉及的元素

N：大整数N，我们称之为模数（modulus）
p 和 q ：大整数N的两个因子（factor）
e 和 d：互为模反数的两个指数（exponent）
c 和 m：分别是密文和明文，这里一般指的是一个十进制的数还有一个就是n的欧拉函数值，在求解d的时候常用

加密过程

选择两个不相等的大素数p和q，这里选61和53（实际应用中，越大越难破解）计算出模数 n = p * q = 61 * 53 =3233计算 φ(n) = (p−1) * (q−1) 即 n 的欧拉函数，φ(n) = 60 * 52 = 3120随机选择一个 e 满足 (1<e<φ(n))，且 e 和 φ(n) 互质，在 1 到 3120 之间选择，选择了 17（实际应用中常常选择 65537 ）取 e 对于 φ(n) 的模反数 d，计算方法: e * d ≡ 1 (mod φ(n)) 即：e*x+φ(n)*y = 1
17x+3120y=1，解得一组整数解为(x,y) = (2753,-15)，即 d = -15将 n 和 e 封装为公钥（3233,17），n 和 d 封装为私钥（3233,2753）对明文A进行加密：B≡A^e (mod n) 或 B = pow(A,e,n)，得到的B即为密文

对密文B进行解密，A≡B^d( mod n) 或 A = pow(B,d,n)，得到的A即为明文

RSA工具

RSA-tools2使用

P 第一个大素数
Q 第二个大素数（P、Q长度不能相差太大）
E 公钥（随机数，必须满足：gcd(E,(p-1)*(q-1))==1）即 E 与 (p-1)*(q-1) 互质
N 共用模数，由 P 和 Q 生成：N=P*Q
D 私钥：D=E^(-1) mod ((p-1)*(q-1))

使用步骤

1、单击“Start”按钮，然后随意移动鼠标直到提示信息框出现，以获取一个随机数种子
2、在“KeySize(Bits)”编辑框中输入 32 ；
3、单击“Generate”按钮生成；
4、复制“1st Prime(P)”编辑框中的内容到“Public Exponent(E)[HEX]”编辑框；
5、再次重复第 1 步；
6、在“KeySize(Bits)”编辑框中输入您所希望的密钥位数，从32到4096，位数越多安全性也高，但运算速度越慢，一般选择1024位足够了；
7、单击“Generate”按钮生成；
8、单击“Test”按钮测试，在“Message to encrypt”编辑框中随意输入一段文本，然后单击“Encrypt”按钮加密，再单击“Decrypt”按钮解密，看解密后的结果是否和所输入的一致，如果一致表示所生成的RSA密钥可用，否则需要重新生成；
9、到此生成完成。其中：
“Private Exponent(D)”编辑框中的内容为私钥；E8D85AA7
“Public Exponent(E)[HEX]”编辑框中的内容为公钥；15E03
“Modulus (N)”编辑框中的内容为公共模数。19F834DB9
请将上述三段十六进制文本保存起来即可。

大整数分解

yafu-x64.exe

cmd 下打开

factor(需要分解的整数)

如果命令行不支持太长的数的话，把 N 保存在文件里，比如：rsa.txt

yafu-x64.exe "factor(@)" -batchfile rsa.txt

eof; done processing batchfile报错

rsa.txt用notepad++打开，最后加上换行即可。

msieve.exe

msieve.exe 0xA41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7 -v

msieve.exe –help 查看帮助
-v 意思打印具体分解的情况
-q 仅仅打印能找到的因子

openssl

-in 选项指定待解密的数据文件msg.bin.enc
-out 选项指定解密后的输出文件msg.bin.dec
-inkey 选项指定用于解密的私钥Key.pem，由于输入是私钥，所以不再需要使用选项-pubin
-decrypt 选项表明这里是进行解密操作
-pkcs 选项指定解密处理过程中数据的填充方式，对于填充，可选项有：-pkcs, -oaep, -ssl, -raw，默认是-pkcs，即按照PKCS#1 v1.5规范进行填充

openssl genrsa -out key.pem -f4 2048
生成私钥，并导出公钥生成2048 bit的PEM格式的RSA Key：Key.pemopenssl rsa -in key.pem -pubout -out key_public.pem
从私钥导出公钥：Key_public.pemecho "hello rsa" > msg.txt
为了简便起见，这里将字符串”hello rsa”存放到文件msg.txt作为测试数据openssl rsautl -in msg.txt -out msg.txt.enc -inkey key_public.pem -pubin -encrypt -pkcs
使用公钥key_public.pem对测试数据msg.txt进行加密生成msg.txt.encopenssl rsautl -in msg.txt.enc -out msg.txt.dec -inkey key.pem -decrypt -pkcs
使用私钥key.pem对加密后的数据msg.txt.enc进行解密，并将结果存放到msg.txt.dec文件中

例子

实验吧 RSA

http://ctf5.shiyanbar.com/crypto/RSA

openssl rsa -pubin -text -modulus -in public.pem

分析公钥得到 N 、E
Exponent（E）= 65537 (0x10001)
Modulus（N）= A41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7

分解大整数

msieve.exe 0xA41006DEFD378B7395B4E2EB1EC9BF56A61CD9C3B5A0A73528521EEB2FB817A7 -v

得到：

p39 factor: 258631601377848992211685134376492365269
p39 factor: 286924040788547268861394901519826758027

使用 python 脚本解密 rsa.py，用到的库 win10 上没装好，在 kali 里可以,用 kali 运行 python2 rsa.py 得到私钥 private.pem

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()