- UID
- 2198
注册时间2005-6-29
阅读权限255
最后登录1970-1-1
副坛主
该用户从未签到
|
复习了下,参考文章是这两篇:
// 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
|
评分
-
查看全部评分
|