RSA 小结 ...

Nisy · 发表于 2016-1-16 00:48:52

复习了下，参考文章是这两篇：

// RSA算法原理
// http://www.ruanyifeng.com/blog/2 ... rithm_part_one.html
// http://www.ruanyifeng.com/blog/2 ... rithm_part_two.html

欧拉函数：给定的正整数n，求小于等于n的正整数中，有多少个与n互质关系。

φ(n)求解：
1> n = 1; ==> φ(n) = 1;
2> n 为质数，φ(n) ==> n-1
3> n = p^k (p为质数，k为大于等于1的整数) ==> φ(p^k)=p^k(1-1/p)
4> n = p1 * p2 (互质整数之积) ==> φ(n)=φ(p1)φ(p2)
5> n = p1^k1 * p2^k2 ...pr^kr (任意大于1的正整数，都可以写成一系列质数的积)
==> φ(n) = φ(p1^k1)φ(p2^k2)...φ(pr^kr)
==> φ(n) = p1^k1 * p2^k2 ...pr^kr(1-1/p1)(1-1/p2)...(1-1/pr)
==> φ(n) = n(1-1/p1)(1-1/p2)...(1-1/pr)

欧拉定理：若a与n互质则 a^φ(n)≡1(mod n)
费马小定理：若a与p互质则 a^(p-1)≡1(mod p)

模反元素：若a和n互质，一定可以找到b，使得ab-1被n整除，则b叫a的模反元素。
==> ab≡1(mod n) <==> a^φ(n)=a * a^(φ(n)-1) ≡ 1(mod n)

====================================
RSA:

N: n = p * q
E: 1 < e < φ(n)
D: e 对于 φ(n) 的模反元素 d
φ(n) = (p-1)(q-1)
==> ed≡1(mod n)
==> ed - 1 = φ(n)y
==> ex + φ(n)y = 1 (已知 e、φ(n)，求 x,y)
==> 求 x,y x即为 d

加密： n,e 公钥
m^e ≡ c(mod n) ==> c = m^e (mod n)
解密： n,d 私钥
c^d ≡ m(mod n) ==> m = c^d (mod n)

加密数据：公钥加密，私钥解密 // 只有我才能解密
签名文件：私钥加密，公钥解密 // 证明是我加密的讯息

公钥是给别人的
如果你想发送加密数据，那你用公钥加，即便被拦截了他们也无法解密。
如果你想把文件签名，所有人都可以解，解密的结果可以证明是否为你的签名。

-------------------------------------------------------------------------

用工具来算一组：

E: 10001
P:
B9496C7A2F3891D019927F5035FCCBA156E41CDFE3C1960CDD3F9E199FB9135C842DD1A7BEFFA8D79F32528D319444DC798392514C58E0369B4E34ED7895EB43
Q:
8798CBB3DD962F635965DA3A1B76A3E54571523E26C90F49FCC20C7DF852CB29D12A629628C98B4D8D671D1CFA72A19A0C6FDF9F0A17DC54CB12CA51F2955653
N:(R)
62244F3C3F2FB1539E988A7A87A6921B25C4AC332279AE05B69F865BA92AE6F58EE7FD05D93836F86B8554303D2213CAFA98CD9556D05C22C17C664CCD65A8D931CA9545DBC11282C73200DF757F5A6005478E0BA17D9DA5944F285E25FADC0EB371D9B55DB1C19C15B77EE4CAD4FE8DCC9FC8CCC3F29ECC0920255AB9A2C8B9
D:
5D733D8F9C8B094B1A451DF7369BC19BE006BA01A6DE3E7A6A3ED46D0B5432BFB7E7E6E25EC84C6F97D2492BF5CA3116A23045F1E1CC5D2F2B160D432C819498AA6857DC87CDECE6A0C8953159358FD69D3B8F7FA4B08F084815E9A1DB1CAA85E334807E93E37070BDE1459708082EA05B47571E6597BB9CD85B3329E539A391

M;
B9496C7A2F // 字符串“B9496C7A2F” 相当于 HEX 内存值：42393439364337413246
C:
3DDFB25DF7A8654C5456E94C1E59659B19D388E9086D79B08D69BBD4E209E94ECDA1602FA79092BD839BC97A8221389CB01D71231C4F0509B0BB4A144955466CBD7E61A2B63C0351B8EB197758CE9237B663C5F6500D7C259A32CA81554A978E05E2328980526E75748A070B47D1C4460EF17F24B841AF15FC4096C2A404EA2F

但是我调用OpenSSL时，RSA_public_encrypt 函数获取的加密值就很诡异了 ... 是因为我哪里参数设置的问题么，还是 ...

VOID TestRsa()
{
const char * ccP = "B9496C7A2F3891D019927F5035FCCBA156E41CDFE3C1960CDD3F9E199FB9135C842DD1A7BEFFA8D79F32528D319444DC798392514C58E0369B4E34ED7895EB43";
const char * ccQ = "8798CBB3DD962F635965DA3A1B76A3E54571523E26C90F49FCC20C7DF852CB29D12A629628C98B4D8D671D1CFA72A19A0C6FDF9F0A17DC54CB12CA51F2955653";
const char * ccN = "62244F3C3F2FB1539E988A7A87A6921B25C4AC332279AE05B69F865BA92AE6F58EE7FD05D93836F86B8554303D2213CAFA98CD9556D05C22C17C664CCD65A8D931CA9545DBC11282C73200DF757F5A6005478E0BA17D9DA5944F285E25FADC0EB371D9B55DB1C19C15B77EE4CAD4FE8DCC9FC8CCC3F29ECC0920255AB9A2C8B9";
const char * ccD = "5D733D8F9C8B094B1A451DF7369BC19BE006BA01A6DE3E7A6A3ED46D0B5432BFB7E7E6E25EC84C6F97D2492BF5CA3116A23045F1E1CC5D2F2B160D432C819498AA6857DC87CDECE6A0C8953159358FD69D3B8F7FA4B08F084815E9A1DB1CAA85E334807E93E37070BDE1459708082EA05B47571E6597BB9CD85B3329E539A391";
const char * ccE = "10001";
//char szIn[0x80] = {0xB9,0x49,0x6C,0x7A,0x2F}; // 计算 Error
char szIn[0x80] = "B9496C7A2F";
unsigned char szOut[0x80] = {};
unsigned char szEnc[0x80] = {};
RSA* pRSA1 = RSA_generate_key( 1024 ,RSA_F4,0,0);
BN_hex2bn(&bN,ccN);
BN_hex2bn(&bD,ccD);
//BN_hex2bn(&bP,ccP);
//BN_hex2bn(&bQ,ccQ);
pRSA1->d = bD; // 私钥
pRSA1->n = bN;
//pRSA1->q = bQ;
//pRSA1->p = bP;
int n = RSA_public_encrypt(0x80,(const unsigned char *)szIn,szEnc,pRSA1,RSA_NO_PADDING);
int m_ = RSA_private_decrypt(0x80,(const unsigned char *)szEnc, szOut, pRSA1,RSA_NO_PADDING);
n = RSA_private_encrypt(0x80,(const unsigned char *)szIn,szEnc,pRSA1,RSA_NO_PADDING);
int a = 0;
}

复制代码

代码调用OpenSSL计算的结果:51AF327C94E0A969D747C1CFD24BE63764FC47A6BA35ABAE8C2E4ED84385CA3A06C4E2A8CF5E22023D042CB53CCA5EDDBD8B9500FE6F2ACBCFC66AE064ADB1E79E4E35CD4AB0DF149B01D8342EC7CE7C8FD63CE99F0E827A5BA9535CF2FBCED425FAAC13CE696592ED524EA948775872D9E388A46D3BBBDD6042DE1F88BCE631

为什么 OpenSSL 的计算结果和大数运算器中的不同呢 ... 这是为啥呢 ... ???

我们能猜到的我们输入的数据不足 0x80，所以可能是填充数据问题造成的，于是我们输入：

char szIn[0x81] = "1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF";

OpenSSL结果：
0x002AEFAC  43 43 3f d8 3d df 64 ac 46 e5 fb a5 5b f9 8b 89
0x002AEFBC  f1 37 fc 25 60 50 1d 05 20 2c 6a d0 fd d8 ed e3
0x002AEFCC  d9 dd 58 46 67 90 f7 e5 c3 09 b8 42 47 f1 bd 0d
0x002AEFDC  a4 18 21 8c 2a f1 02 6d 05 87 46 e9 a6 6d 98 70
0x002AEFEC  6c c7 07 42 4e 5f 48 55 8a 9d e7 ff 8d 3a 8e 73
0x002AEFFC  74 6a f3 3c 80 ec 38 24 fc 12 0c 36 f9 1b d7 53
0x002AF00C  0e 2d 4d ec 63 f6 dc 13 b4 7b 3d ab ec 50 f7 11
0x002AF01C  fc 95 53 30 b1 53 d1 f5 58 22 a3 a4 78 54 d4 21

OK 这下两组结果完全吻合了 ~ 那我们在OpenSLL中填充的为0，RSA工具中填充的是什么呢？要么去动态调试要么我们就来修改我们的填充值。总之归其原因两者参与运算的数据肯定是不同的。

我们再继续去猜，由于RSA的运算过程中是使用大数类来进行操作的，我们输入的0x80的数据在作为一个大树来直接使用的，初始化的时候是执行了倒叙操作，而这样就导致了我们的0x80数据在变成大数时成了成了其他的值。
char szIn[0x80] = "B9496C7A2F";

初始化时：
0x002BF1F4  42 39 34 39 36 43 37 41 32 46 00 00 00 00 00 00  B9496C7A2F......
0x002BF204  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF214  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF224  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF234  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF244  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF254  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF264  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
倒序转为大数后：
0x002BF1F4  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF204  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF214  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF224  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF234  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF244  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF254  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF264  00 00 00 00 00 00 46 32 41 37 43 36 39 34 39 42  ......F2A7C6949B

而我们希望其转变为大数后的值是这个样子的：
0x002BF1F4  46 32 41 37 43 36 39 34 39 42 00 00 00 00 00 00  F2A7C6949B......
0x002BF204  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF214  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF224  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF234  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF244  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF254  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x002BF264  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

so ... 我们自己代码中的赋值和我们借用工具参与计算的值已非同一个数值了 ...
所以我们将代码修改为：

char szData[] = "B9496C7A2F";
char szIn[0x80] = {};
int nLen = strlen(szData);
memcpy(szIn + 0x80 - nLen,szData, nLen);

复制代码

然后就柳暗花明又一村了 ^_^

这个问题其实也是让我疑惑了很久了，包括发帖的时候还在分析其原因是什么，包括刚才OD去动态调试，后来突然想到大数的倒序，然后进一步的去验证，才找到了真正的原因所在。遇到问题不放弃不言败，不忘记这个目标终究会找到问题答案。

文中提到的工具下载：
加密解密小玩具 v0.3 By: lucky_789
https://www.chinapyg.com/thread-74935-1-1.html
BigIntCalc_v1.13 by: readyu
http://tools.pediy.com/windows/C ... Calc/BigIntCalc.rar
RSATool2 v1.70
http://tools.pediy.com/windows/C ... ool/RSATool.1.7.rar

lucky_789 · 发表于 2016-1-16 01:36:05

RSATool只能把明文作为“字符串”来处理。缺点：当明文为不可见字符时就无法输入，也就无法计算。
Big Integer Calculator只能把明文作为“大数”来处理。缺点：当想用字符串作为明文时，需要先转换为内码串再输入，麻烦。
小玩具既可把明文作为“字符串”来处理，也可把明文作为“大数”来处理，即：既可计算内码表示的明文，也可计算字符串明文。根据需要选择。更灵活！

ZMLoveLH · 发表于 2016-1-16 01:03:03

我是菜鸟，老实说看不懂

pentium450 · 发表于 2016-1-16 01:48:01

lucky_789 发表于 2016-1-16 01:36
RSATool只能把明文作为“字符串”来处理。缺点：当明文为不可见字符时就无法输入，也就无法计算。
Big Int ...

我举双手赞成！

lucky_789 · 发表于 2016-1-16 02:18:01

没有深入研究openSSL，你确定初始化N\D等的函数是BN_hex2bn吗？可你用的却是字符串

Nisy · 发表于 2016-1-16 03:16:00

lucky_789 发表于 2016-1-16 02:18
没有深入研究openSSL，你确定初始化N\D等的函数是BN_hex2bn吗？可你用的却是字符串

找到问题原因，已更新帖子。

dliwj · 发表于 2016-1-16 15:36:23

校长把这三个小工具分享下吧
感谢+祝福，
分享有质量的文章

bbaa987 · 发表于 2016-1-16 15:59:14

研究这个对破解软件有用吗？

微若清风 · 发表于 2016-1-17 18:04:28

我是菜鸟，老实说看不懂

lucky_789 · 发表于 2016-1-17 23:07:56

也简单测试了一回，感觉下面这几个函数中的长度值（1024、0x80）没影响到结果的运算，比如把1024改为64也一样的结果啊

RSA_generate_key( 1024 ,RSA_F4,0,0);
RSA_public_encrypt(0x80,(const unsigned char *)szIn,szEnc,pRSA1,RSA_NO_PADDING);
RSA_private_decrypt(0x80,(const unsigned char *)szEnc, szOut, pRSA1,RSA_NO_PADDING);
RSA_private_encrypt(0x80,(const unsigned char *)szIn,szEnc,pRSA1,RSA_NO_PADDING);

		自动登录	找回密码
密码			加入我们

[原创] RSA 小结 ...

评分

点评

点评

点评