公钥和私钥的产生
N = 17 * 53 = 901
m = (17-1)*(53-1)=832
let e=17 // by random
d = 49 // because ( d * e ) % m = 1 , that is ( d * 17 ) % 832 = 1
公钥(901,17) 私钥(901,49)
加密过程
int text = 123 (注意，消息必须比N小);
由于 text^e % N = code, 即123^17 % 901 = code
得到 code = 378
解密过程
int code = 378;
由于 code^d % N = text, 即378^49 % 901 = text
得到 text = 123
继续测试 text=456，text=789
pow=337587917446653715596592958817679803
remain is encrypted msg, 378
pow=1981975090781375567648692626283639181924626345824851461901652399140883944715714801363950285365649593405611421793924739086942208
remain is decrypted msg, 123
pow=1593684413895892775431288016392119629314523136
remain is encrypted msg, 31
pow=11932267966476130911517907186867185074148138371734008968629799047943267871
remain is decrypted msg, 456
pow=17795453274736834362412998969384875211516379055829
remain is encrypted msg, 24
pow=42692426938810341355395254247148178158685421582623594902764046516224
remain is decrypted msg, 789
如果取随机私钥为23，由(d*e)%832=1得到, d=1447
密钥对(901,23) (901,1447)
加密过程2
int text = 123 (注意，消息必须比N小);
由于 text^e % N = code, 即123^23 % 901 = code
得到 code = 149
./rsa 123 23 901
pow=1169008215014432917465348578887506800769541157267remain=149
解密过程2
int code = 149;
由于 code^d % N = text, 即149^1447 % 901 = text
得到 text = 123
./rsa 149 1447 901
pow=3985936655027786133408829502155172486035904622712472852621608241746913310297391658184716646894437322554704092666282273452855275384085318288046586224429347497827880247547339473036917816909223107117175531587260639648846353409844711958706092093596730245565996912003513233565007065727967455584025260911486810746630678094905762197449698418393359848248040053204101912486274919097714199485366154899138632699959288422245852748033196204793416492537560971606021510788711927751466478702987029084746015114294265995598688131965702319407549561404014161346291768678253671588393974329706005805322594725598901652699451931023169921356303019131994689149252324743527490479491940886193543681983109194838286138082417166699477848202718347964687820796592019328071391913496121999081649165198851436538061394347514783202440077109779016851948752385464899137550781743050874740569187871261877899262047556241037569513727241777013958245104990221096084832705392187584307190592892229359969096765098092852369655657703699448285550244408917771734036376812464079731831055765945558390839789584335008109083209997253493029025530744552730080488782762304788784814726079959495953838029404233253982382231821825059796386932843561833899624385090559266388309444170895176942274476213381834239263776359183712755409616899578532221617869355630180167696863598518217920559059880617368830175766115161601439972079153451714153741788486717251510899260246046823014371599692024285779413561563126708199148100439542764252953767607725285544447473028149388111275729639654549626974834654173824045613468737321214142959704129737498708807684383933171830693895907145483744154610946805717856953750819840697171152907340638764324070540105234490652588160359246349466614681404427878668385500329188714136429101735281721801482418741695141767516243529016466547669220693256890471638180522587977329481861127690785609948263132745032373176370846812221619669962814451607786769451764283956667048224778080078119822225893910169294528225164973914039173067841802331919352006767688214788854741209476129408348246067157963999292702077540465878741199438072301716437512437206906827652022918225801876338146245435414504850134452701815858979786932044372642085983768077238865428181442964225497161921056275373467702146501770271202169524135998423744124666111748049368433360408756284224496271587223056244362621755475005116811157719670973646470109741830322978187377451183707774175105440143172725174869125803081026121461473916991813456601031329814195352576206287933278596520860904193983118052847549233481720087449879783102557667902374897959615060335464554488838194211827049636607371477869631641345731986506361643642064555937668953135519546086134667128658277195852003986966590034063953363008297418066438616213070509869485074973762746760573414761610051773364844423773838759134377078566230721304823672091660155346094353132676209154505265788271907294843328075680525047092758196227733579042369746326640103471517003588082621099265771434203691296983507676617026988511984284930947929603040015756972741093414371038843713030209328408570065664368532865353731976350820941739288708181549678167180213092260955630329359228466794631319443883593072931779043019549
remain=123
解密的优化（中国余数定理)
dp = d mod (p − 1) = 1447 mod (17− 1) = 7
dq = d mod (q − 1) = 1447 mod (53− 1) = 43
qInv*q mod p = 1 即 qInv * 53 mod 17 = 1 得到 qInv=9
m1=code^dp mod p = 149^7 mod17 = 4
m2=code^dq mod q = 149^43 mod 53 = 17
h= (qInv * (m1-m2))mod p = (9 * (-13)) mod 17 = 2
r= m2 + h*q = 17 + 2*53= 17 + 106 = 123
和上面没有优化的解法得到的结果一样。
演示程序
用c语言编写，大数计算库使用的是开源的GMP库，下载地址如下：
最常用的算法：x的n次方取m的模代码
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
int main(int argc, char * argv[])
{
mpz_t pow, mod;
mpz_init(pow);
mpz_init(mod);
mpz_ui_pow_ui(pow, atoi(argv[1]), atoi(argv[2]));
printf("pow=");
mpz_out_str(stdout, 10, pow);
printf("\n");
mpz_mod_ui(mod, pow, atoi(argv[3]));
printf("remain=");
mpz_out_str(stdout, 10, mod);
printf("\n");
return 0;
}
项目文件
http://hi.csdn.net/attachment/201201/20/0_1327043412h7wW.gif
ASN.1 规范定义的rsa公钥私钥保存结构
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
为什么要存储exponent1, exponent2？
答案：为了使用“中国剩余定理”优化计算过程
It has to do with optimizing RSA.
It turns out that using the Chinese Remainder Theorem with p, q, d(mod p−1), and d(mod q−1) (i.e., prime1, prime2, exponent1, exponent2 from the data structure in the question) to run the decryption operation faster than if you only had d,n.
openssl输出一个RSAkey信息 openssl rsa -in cakey.pem -text -noout
Private-Key: (2048 bit)
modulus:
00:d0:d8:21:b2:85:7b:23:b2:5f:48:2b:36:ac:46:
95:9e:5e:5b:77:1a:8a:95:6a:e1:ac:ef:dd:78:2a:
78:41:bc:4f:b6:0c:79:c7:59:5d:15:18:11:68:ab:
83:a1:2e:54:1a:cc:d6:89:59:3e:48:ea:13:7d:ad:
be:06:10:cb:3c:77:17:b8:1f:df:c6:44:39:22:1d:
3d:b6:09:b6:3e:8b:ac:04:b9:01:8c:ea:94:08:bb:
d9:66:ca:81:f3:f3:aa:6a:de:ab:ca:c9:50:12:55:
00:83:1c:59:51:b5:8b:b8:a9:0e:d6:fa:33:65:db:
0a:e6:db:27:ca:c2:7f:a8:dd:47:27:fe:a3:5a:84:
8c:9e:c3:20:c7:3d:74:ad:42:6f:8d:24:ab:e7:b8:
6e:be:b8:a8:af:c4:26:f1:93:48:7a:55:0a:8b:e0:
89:07:2d:3f:90:7c:40:39:05:60:a3:54:6f:24:7a:
db:7a:53:3b:95:cc:10:62:cf:05:4a:d3:8b:16:36:
4f:38:58:95:49:37:39:22:7e:50:4f:89:6b:1d:67:
62:d6:05:ec:85:33:07:8b:7c:aa:47:85:4f:a5:ba:
27:f1:ac:5f:82:25:3f:e1:1e:f1:46:e9:28:ae:e1:
3b:96:e3:eb:da:70:a2:db:a9:58:97:30:3b:27:64:
78:e9
publicExponent: 65537 (0x10001)
privateExponent:
79:4c:0e:c6:51:20:a4:2b:05:8c:35:0d:1c:22:22:
e4:48:89:77:33:c3:29:e5:5a:0d:c7:83:2a:38:00:
80:ad:8e:de:7d:80:7d:78:39:c7:f6:a2:a5:d8:78:
2b:35:6d:43:e3:94:f7:51:0e:0b:eb:68:46:a6:92:
a7:93:39:77:74:f4:21:cc:e1:7b:96:44:58:bc:03:
0b:a7:b8:61:bb:5d:bd:a0:76:76:12:08:c8:c9:d2:
0b:11:b3:48:ad:4d:5d:a4:d6:c2:81:0a:30:9b:8e:
20:98:66:88:3e:99:58:37:58:97:23:da:96:5e:12:
86:e2:e2:c9:b1:0d:d4:55:23:59:1c:44:1e:0c:01:
4d:0a:1d:1b:0e:4c:45:ed:d9:e6:43:9b:af:f4:fc:
3c:78:3c:7b:22:c2:b4:70:61:8b:d1:e8:33:f9:f5:
a6:15:80:a5:06:d9:8b:97:d9:45:25:60:58:65:a8:
8a:e5:77:a4:9a:c6:ad:03:46:12:61:e0:f4:98:1b:
4a:ca:62:b1:c4:8c:c8:63:6e:10:6f:cc:af:de:b8:
1f:b2:06:f6:d2:3f:8f:85:ea:cc:63:37:e0:b3:fd:
17:d2:68:ca:12:68:35:32:c7:40:c7:7e:56:27:ae:
df:df:b0:d5:47:23:10:e9:ac:e9:c0:5a:be:36:f8:
01
prime1:
00:fb:f6:59:4a:66:53:9d:4a:cd:e0:5d:77:5a:d0:
d1:88:f8:f8:f3:b6:e2:1f:12:56:e8:6a:3d:5e:24:
bd:21:02:45:b3:d6:88:1a:f5:21:67:17:40:1e:d9:
4e:63:54:b5:88:9e:a8:6f:a6:20:d6:ef:11:14:7b:
a3:c7:04:c7:5c:55:21:8b:eb:40:ba:1d:a7:d2:4b:
f5:33:22:d6:77:7d:9c:4a:3e:5a:1c:e3:34:e7:e4:
6b:a1:15:e6:6a:3c:68:ab:65:65:95:92:12:91:dd:
7d:8f:0f:49:a6:41:c7:07:a9:75:a4:32:7f:01:e8:
e0:2b:a3:1b:15:e3:0a:75:b9
prime2:
00:d4:30:e5:2d:84:b5:4c:22:0f:02:65:64:8f:04:
9e:50:01:d7:20:54:e1:a2:bc:b5:4d:6e:50:ac:05:
33:d7:38:02:81:9a:c0:6c:22:1c:cd:6d:3d:6e:67:
ab:1e:af:95:b7:83:4e:7c:b8:3b:6a:49:6a:f4:88:
83:ad:2d:ff:5a:d4:7f:4b:ba:99:a6:09:9d:66:89:
29:f1:e3:dc:d4:a2:9f:3e:e9:62:97:b9:7f:35:ea:
64:78:71:fb:d7:49:d1:1f:ec:e9:7d:05:84:f1:c1:
97:b9:08:7f:c5:5f:d3:78:6c:4f:7f:cb:4b:1a:46:
bd:ff:bc:25:0a:96:fb:b4:b1
exponent1:
00:df:e1:a8:bb:84:2a:fd:d3:af:15:92:d7:70:19:
a6:65:d8:1c:95:a9:c6:48:a7:aa:13:7f:fb:21:80:
f1:90:b8:0d:29:5c:11:ba:2a:60:50:d3:07:05:a2:
3f:95:e1:7a:20:78:21:e0:7b:34:28:e7:6a:3c:d2:
13:d7:ce:76:3a:a3:e6:58:06:64:90:3b:b3:98:18:
28:3b:14:d4:8e:7e:4d:76:66:ea:f9:4a:26:03:7b:
22:eb:92:a3:17:78:af:e4:c4:07:3c:9c:fb:e5:22:
72:e3:c0:48:c7:f3:20:9f:bd:42:ab:f0:b6:8c:02:
d9:d5:cc:6b:4f:ca:5a:cb:f9
exponent2:
67:ac:0c:0d:15:4d:cf:08:c4:f4:92:bd:72:f2:fa:
b6:74:6f:bb:28:3d:a5:d9:35:6b:c3:7e:3e:cd:bb:
ea:67:3f:32:3b:7d:d0:57:4a:63:44:00:43:b4:fa:
f2:5f:2f:73:1e:00:77:07:3c:60:4d:c6:a7:fb:1a:
fa:be:02:89:4a:51:77:9a:8f:ff:83:ab:17:b1:e4:
80:7e:a8:22:6b:e2:0a:46:d5:18:f4:54:a6:ef:02:
6f:a6:a1:39:2a:a3:b6:49:76:3a:d3:3b:85:32:e5:
02:4e:98:be:c2:76:fb:db:4f:6c:4c:d3:40:df:57:
6d:5f:6b:69:a5:23:0d:c1
coefficient:
3b:2d:72:9f:e6:cf:f3:95:a8:94:ee:e7:e1:b2:6e:
0e:36:87:39:a6:b7:4f:68:6f:f4:7b:b1:37:73:77:
66:1d:4d:8c:ca:86:86:b9:02:0c:78:a5:d8:65:62:
77:ce:1f:8c:2a:01:01:33:1f:5f:6e:db:4a:ac:97:
8a:87:34:1c:50:d1:a9:17:33:69:b1:72:99:45:c3:
85:1e:7c:73:7c:17:a7:a5:2f:99:da:a8:c9:65:86:
96:26:4f:0f:1c:b6:cf:6e:8f:78:82:2a:9d:ff:84:
d9:d8:c8:0d:d0:2e:09:23:43:7a:ee:b0:f3:36:75:
1b:28:1a:ba:06:0a:a3:8a
RSA的安全性
RSA的公钥就是一个模数 N以及一个随机数（甚至就是著名的0x10001, 65537)，所以如果N冲突怎么办(甚至2个N共享同一个分解因子）怎么办？
First, what matters is not having two identical private keys, if either of the prime numbers is the same in the modulus (which is part of the public key), it is easy to quickly recover the full private key.
(Aside -- Brief RSA primer: In RSA for an n-bit private key, the public key is composed of an exponent, typically e=65537 and a modulus, N, which is the product of two n/2-bit prime numbers. The private key consists of the private exponent d (calculated by d = e-1 mod (p-1)(q-1) which is efficiently found using the extended Euclidean algorithm) and the modulus, N. The public pair allows encryption of a message, m, into a ciphertext, c, via modular exponentiation: c = m^e mod N, and the private key allows decryption via m = c^d mod N. This all works due to a fundamental part of number theory -- Euler's theorem and how to calculate totients).
If two moduli share a factor, then you can take the greatest common divisor of the two moduli efficiently (using Euclid's algorithm) and find the shared factor. Let, the two moduli share a prime factor q, so N1 = p1 q and N2 = p2 q, then gcd(N1, N2) = q. With the found prime factor, it is trivial to find the other prime factor (p1 = N1/q) and to recreate the private exponent. A 2012 study looked at 4.7 million distinct RSA moduli and found shared factors in 12720 of them (that is 0.3% of the 4.7 million RSA keys trawled from the web are broken from their analysis). (The paper also found several other problems with RSA in practice, like shared keys used on seemingly different entities.)
Now, choosing identical prime numbers is extremely low probability if your machine has a high amount of initial entropy and there is no flaw in the random number generation. Both of these assumptions aren't always true; see the Debian OpenSSL problem keys from 2006-2008 and note that many people create keys for systems on brand new (virtual) machines that haven't had enough time to establish a lot of entropy.
Roughly, the strength of a 1024-bit key relies on the choice of the two 512-bit prime numbers that comprise the modulus. By the prime number theorem there are roughly (2512/ln 2512 - 2511/ln 2511) ~ 10151 distinct 512 bit prime numbers. From the birthday paradox, you should expect to have a collision of a prime number showing up more than once with about 50% probability, after generating sqrt(10151) ~ 1075 distinct prime numbers. That is if some government generated a billion 512-bit prime numbers per second per computer and used a billion computers and had this run for a billion years they would only have generated about 1034 prime numbers, and the probability of a collision with some external key would be essentially zero, the same chance as playing powerball exactly 10 times on consecutive weeks and buying exactly one ticket and winning the jackpot every single time without cheating. (It doesn't get significant chance of a single prime collision until nearly 1040 = 10000000000000000000000000000000000000000 times more prime numbers are generated).
However, as the 2012 paper shows, this is not true in the real world as RSA keys are generated by flawed methods in practice at a rate of at least 0.3%.
http://windowsontheory.org/2012/05/17/factoring-rsa-moduli-part-ii/
问题1：为什么openssl rsautl -sign 的结果和openssl pkeyutil -sign ( or, openssl dgst -sign)的结果不一样？
edit - a little more explanations:
let's create a digest and show it
$ openssl dgst -sha256 -binary < data.txt > digest
$ hd digest
00000000 26 3b 0a a1 2e b9 32 db b8 dc d3 6f 37 94 0b 05 |&;....2....o7...|
00000010 71 9c ba 79 46 34 28 9f 5c 5b 98 9a 64 61 c9 ec |q..yF4(.\[..da..|
now we take this digest and sign int using rsautl:
$ openssl rsautl -sign -inkey private.pem < digest > sign1
$ hd sign1
00000000 1b 7a cf a4 8d 41 8e 04 ed 3a bb ba 86 f1 f8 e0 |.z...A...:......|
00000010 df f7 47 3e d7 a7 f4 90 7a 05 f8 7f 45 e5 29 e7 |..G>....z...E.).|
00000020 9f f4 2c 91 97 2f e7 26 69 9f 6a 07 a3 48 1b 85 |..,../.&i.j..H..|
00000030 2e f8 ee 44 4d 25 9f ae 05 95 81 c9 e3 07 68 ad |...DM%........h.|
now let's sign the same file using dgst directly:
$ openssl dgst -sha256 -sign private.pem < data.txt > sign2
$ hd sign2
00000000 15 c2 94 87 eb e6 cb 45 c8 63 0c 97 60 d3 07 f3 |.......E.c..`...|
00000010 dc 65 32 ad 44 1c c2 2a 7f a3 e1 fc dd 84 27 8c |.e2.D..*......'.|
00000020 77 a6 97 2b 33 6b c6 d7 7d e1 1d 39 5c 48 b6 48 |w..+3k..}..9\H.H|
00000030 cb 18 be bf 6a 66 90 d3 88 89 52 6c dd d1 b9 99 |....jf....Rl....|
So what's different here? To see that, we can verify the signature and show the raw output. Both files do contain the digest, but the metadata and padding is different:
$ openssl rsautl -raw -verify -inkey private.pem < sign1 | hd
00000000 00 01 ff ff ff ff ff ff ff ff ff ff ff ff ff ff |................|
00000010 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff 00 |................|
00000020 26 3b 0a a1 2e b9 32 db b8 dc d3 6f 37 94 0b 05 |&;....2....o7...|
00000030 71 9c ba 79 46 34 28 9f 5c 5b 98 9a 64 61 c9 ec |q..yF4(.\[..da..|
$ openssl rsautl -raw -verify -inkey private.pem < sign2 | hd
00000000 00 01 ff ff ff ff ff ff ff ff ff ff 00 30 31 30 |.............010|
00000010 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 |...`.H.e....... |
00000020 26 3b 0a a1 2e b9 32 db b8 dc d3 6f 37 94 0b 05 |&;....2....o7...|
00000030 71 9c ba 79 46 34 28 9f 5c 5b 98 9a 64 61 c9 ec |q..yF4(.\[..da..|
To see this more clearly, we can try to use the -asn1parse flag, which won't work for the first signature, but for the second it shows the correct structure of the signature:
$ openssl rsautl -verify -inkey private.pem -asn1parse < sign1
Error in encoding
139931349546656:error:0D07209B:asn1 encoding routines:ASN1_get_object:too long:asn1_lib.c:142:
$ openssl rsautl -verify -inkey private.pem -asn1parse < sign2
0:d=0 hl=2 l= 49 cons: SEQUENCE
2:d=1 hl=2 l= 13 cons: SEQUENCE
4:d=2 hl=2 l= 9 prim: OBJECT :sha256
15:d=2 hl=2 l= 0 prim: NULL
17:d=1 hl=2 l= 32 prim: OCTET STRING
0000 - 26 3b 0a a1 2e b9 32 db-b8 dc d3 6f 37 94 0b 05 &;....2....o7...
0010 - 71 9c ba 79 46 34 28 9f-5c 5b 98 9a 64 61 c9 ec q..yF4(.\[..da..
http://*.com/questions/9951559/difference-between-openssl-rsautl-and-dgst
The simple answer is that dgst -sign creates a hash, ASN1 encodes it, and then signs the ASN1 encoded hash, whereas rsautl -sign just signs the input without hashing or ASN1 encoding. Both methods include the input data in the output, together with the signature, rather than producing only a signature as output. Here is a Bash script that shows the difference between openssl dgst -sign and openssl rsautl -sign.
#!/bin/bash# @(#) Bash script demos difference between openssl rsautl and dgst signing# Usage: $0 <name of file to sign> <private key file, without passphrase># 1. Make an ASN1 config filecat >asn1.conf <<EOFasn1 = SEQUENCE:digest_info_and_digest[digest_info_and_digest]dinfo = SEQUENCE:digest_infodigest = FORMAT:HEX,OCT:`openssl dgst -sha256 $1 |cut -f 2 -d ' '`[digest_info]algid = OID:2.16.840.1.101.3.4.2.1params = NULLEOF# If you are wondering what the "algid = OID:2.16.840.1.101.3.4.2.1" is, it's# the SHA256 OID, see http://oid-info.com/get/2.16.840.1.101.3.4.2.1# 2. Make a DER encoded ASN1 structure that contains the hash and# the hash typeopenssl asn1parse -i -genconf asn1.conf -out $1.dgst.asn1# 3. Make a signature file that contains both the ASN1 structure and# its signatureopenssl rsautl -sign -in $1.dgst.asn1 -inkey $2 -out $1.sig.rsa# 4. Verify the signature that we just made and ouput the ASN structureopenssl rsautl -verify -in $1.sig.rsa -inkey $2 -out $1.dgst.asn1_v# 5. Verify that the output from the signature matches the original# ASN1 structurediff $1.dgst.asn1 $1.dgst.asn1_v# 6. Do the equivalent of steps 1-5 above in one "dgst" commandopenssl dgst -sha256 -sign $2 -out $1.sig.rsa_dgst $1# 7. Verify that the signature file produced from the rsautl and the dgst# are identicaldiff $1.sig.rsa $1.sig.rsa_dgst
You can use rsautl that way : (with private key: my.key and public key my-pub.pem)
$ openssl rsautl -sign -inkey my.key -out in.txt.rsa -in in.txt
Enter pass phrase for my.key:
$ openssl rsautl -verify -inkey my-pub.pem -in in.txt.rsa -pubin
Bonjour
With this method, all the document is included within the signature file and is outputed by the final command.
But in my case, my certificate says : Signature Algorithm: sha1WithRSAEncryption. So I would recommend you to use the standard way of signing document in 4 steps: (This method is used for all asymmetric electronic signatures in order not to overcharge the signature file and/or CPU usage)
Create digest of document to sign (sender)
Sign digest with private key (sender)
Create digest of document to verify (recipient)
Verify signature with public key (recipient)
OpenSSL do this in two steps:
$ openssl dgst -sha256 -sign my.key -out in.txt.sha256 in.txt
Enter pass phrase for my.key:
$ openssl dgst -sha256 -verify my-pub.pem -signature in.txt.sha256 in.txt
Verified OK
With this method, you sent the recipient two documents : the original file plain text, the signature file signed digest. Attention: the signature file does not include the whole document! Only the digest.