& ltI > foundation
RSA algorithm is very simple and can be summarized as follows:
Find two prime numbers p and q
Let n=p*q
T=(p- 1)*(q- 1)
Take any number e, and it is required to satisfy e.
Take d*e%t== 1
In this way, three numbers are finally obtained: n d e.
Let the message be m (m
Let c=(M**d)%n get the encrypted message c.
Let m=(c**e)%n then m == M, thus the decryption of c is completed.
Note: * * stands for power, and D and E in the above two formulas are interchangeable.
In symmetric encryption:
N d two numbers constitute a public key, which can be told to others;
Two numbers, n e, make up the private key, and e keeps it for himself and doesn't let anyone know.
The information sent to others is encrypted by E. As long as others can decrypt it by D, it proves that the information was sent by you, which constitutes a signature mechanism.
When others send you messages, they use D encryption, so only those who have E can decrypt them.
The security of rsa is that there is no effective way to decompose a large number n.
Therefore, when n d is known, e cannot be obtained; It's impossible to know n e.
Find D.
< second > practice
Next, let's practice and see the actual operation:
Find two prime numbers:
p=47
q=59
such
n=p*q=2773
t=(p- 1)*(q- 1)=2668
Take e=63 and satisfy e.
With perl's simple and exhaustive method, we can get the number d of the complete principal e*d%t == 1:
c:\ Temp & gt； perl -e "foreach $i ( 1..9999){ print $ I，last if $i*63%2668== 1 } "
847
That is, d = 847.
Finally, we got the key.
n=2773
d=847
e=63
Take the message M=244, let's have a look.
Encryption:
c=M**d%n = 244**847%2773
Use perl's large number calculation to calculate:
c:\ Temp & gt； perl-mbi gint-e " print 244 * * 847% 2773 "
465
That is, after encrypting m with d, encryption information C = 465 is obtained.
Decryption:
We can use e to decrypt encrypted c and restore m:
m=c**e%n=465**63%2773:
c:\ Temp & gt； Perl -Mbigint -e "Print 465**63%2773"
244
That is, c is decrypted by e, and m=244 is obtained, which is equal to the original information m.
< third > string encryption
By integrating the above process, we can realize an example of encrypting and decrypting strings.
Every time the ascii value of a character in a string is taken as m for calculation, the output is encrypted 16.
A number in the form of a string, represented by 3 bytes, such as 01f.
The code is as follows:
#! /usr/bin/perl -w
# Test Program Written by #RSA Computing Process Learning Plan
# Water Cloud 2003-8- 12
#
Strict use;
Use Math::BigInt；;
My% RSA _ CORE =(n =>；; 2773，e= >63，d = & gt847); #p=47，q=59
my $ N = new Math::BigInt($ RSA _ CORE { N })；
my $ E = new Math::BigInt($ RSA _ CORE { E })；
my $ D = new Math::BigInt($ RSA _ CORE { D })；
Print "n = $ n d = $ d e = $ e \ n";
Child RSA_ENCRYPT
{
My $ r _ mess = shift @ _
my ($c，$i，$M，$c，$ cmess)；
for($ I = 0； $ i< length ($ $ r _ mess); $i++)
{
$c=ord(substr($$r_mess，$i， 1))；
$ M = Math::BigInt-& gt； New ($ c);
$ C = $ M-& gt； copy()； $ C->； bmodpow($D，$ N)；
$ C = sprintf“% 03X”，$ C；
$cmess。 = $ c；
}
return \ $ cmess
}
Child RSA_DECRYPT
{
My $ r _ mess = shift @ _
my ($c，$i，$M，$c，$ dmess)；
for($ I = 0； $ i< length ($ $ r _ mess); $i+=3)
{
$c=substr($$r_mess，$i，3)；
$ c = hexadecimal ($ c);
$ M = Math::BigInt-& gt； New ($ c);
$ C = $ M-& gt； copy()； $ C->； bmodpow($E，$ N)；
$ C = chr($ C)；
$dmess。 = $ c；
}
return \ $ dmess
}
My $mess="RSA baby hahaha ~ ~ ";
$ mess = $ ARGV[0]if @ ARGV & gt； = 1;
Print "original string:", $mess, "\ n "；;
my $ r _ cmess = RSA _ ENCRYPT(\ $ mess)；
Print "encrypted string:", $$r_cmess, "\ n "；;
my $ r _ dmess = RSA _ DECRYPT($ r _ cmess)；
Print "Decryption String:", $$r_dmess, "\ n "；;
#EOF
Test it:
c:\ Temp & gt； perl rsa-test.pl
N=2773 D=847 E=63
Original string: RSA baby hahaha ~ ~ ~
Encrypted string: 5cb6cd6bc58a7709470a70aaa70a6c70a46c70a46c70a46c70a46c70a4.
Decryption string: RSA baby hahaha ~ ~ ~
c:\ Temp & gt； Perl rsa-test.pl security focus
N=2773 D=847 E=63
Original string: security focus (xfocus)
Encrypted string: 3393ec12f0a466e0aa9510d025d7ba0712dc379f47d51c325d67b.
Decryption string: security focus (xfocus)
& lt fourth > raise
As mentioned earlier, the security of rsa comes from the fact that n is large enough, but the n we use for testing is very small, which can't guarantee security at all.
We can get enough N and D E through RSAKit, RSATool and other tools.
With this tool, we get the n and D E of 1024 to test:
n = 0x 328 c 74784 df 3 1 1 19c 526d 18098 e bebb 943 b 0032 b 599 ce e 13c C2 BCE 7 b 5 fcd 15f 90 b 66 EC 3 a 85 f 5005d
BDC ded 9 BDF CB 3c 4 c 265 af 164 ad 55884d 8278 f 79 1 c 7 a 6 BF dad 55 EDB C4 f 0 17 f 9 CCF 1538 d4c 20 13433 b 383 b
47d 80 EC 74 b 5 1276 ca 05 b 5d 6346 b 9 ee 5 ad 2d 7 be 7 abfb 36 e 37 108 DD 6043894 1 D2 ed 173 CCA 50 e 1 14705 d7e 2
BC5 1 195 1
d=0x 1000 1
e = 0xe 760 a 3804 acde 1e8e 3d 7 DC 0 197 f 9 cef 6282 ef 552 e 8 cebbb 7434 b 0 19 a9d 87 a 3 106 DD 28 c 523 c 2995
4c 5d 86 b 36 e 943080 e 49 19 ca 8 ce 087 18c3b 0930867 a 98 f 635 EB 9 ea 9200 b 25906d 9 1b 80 a 47b 77324 e 66 aff 2
c 4d 70 D8 b 1 c 69 c 50 a 9d 8 B4 b 7 a3 c 9 ee 05 fff3 a 16 AFC 02373 1d 80634763 da 1 dcab e 986 1a 4789 BD 782 a 592d 2 b
1965
Set the original information
m = 0x 1 1 1 1 1 1 1 1 1 1 1 1 12222222222223333333333
The calculation of such a large number depends on the large number operation library, and the calculation with perl is very simple:
A) encrypt m with d, as follows:
c=M**d%n:
c:\ Temp & gt； perl-mbi gint-e " $ x = Math::BigInt-& gt； bmodpow(0x 1 1 1 1 1 1 1 1 1 1 1 1 1 122222222233
3333333333，0x 1000 1，0x 328 c 74784 df 3 1 19c 526d 18098 ebeb 943 b 0032 b 599 CEE 13c 2 BCE 7 b 5 f
CD 15 f 90 b 66 EC 3 a 85 f 5005 dbdcded 9 BDF CB 3c 4 c 265 af 164 ad 55884d 8278 f 79 1 c 7 a 6 BF dad 55 EDB C4 f 0
17 F9 CCF 1538 d4c 20 13433 b 383 b47 d 80 EC 74 b 5 1276 ca 05 b 5d 6346 b 9 ee 5 ad 2d 7 be 7 abfb 36 e 37 108 DD 6
043894 1 D2 ed 173 CCA 50 e 1 14705d 7 e2bc 5 1 195 1)； Print $ x-& gt；; as_hex "
0x 17b 287 be 4 18c 69 ECD 7c 39227 ab 68 1ac 422 FCC 84 bb 35 D8 a 632543 b 304 de 288 A8 d 4434 b 73d 2576 BD
45692 b 007 F3 a2 f 7 C5 F5 aa 1d 99 ef 3866 af 26 a8e 8767 12ed 1 D4 C4 b 293 e 26 BC 0 a 1 DC 67 e 2477 15 caa6b
3028 f 946 1a3b 1533 EC 0 CB 47644 1465 f 10 D8 ad 47452 a 12db 060 1c5e 8 beda 686 DD 96 D2 ACD 59 ea 89 b 9 1
f 1834580c3f6d90898
That is, the information encrypted by D after M is:
c = 0x 17b 287 be 4 18c 69 ECD 7c 39227 ab 68 1ac 422 FCC 84 bb 35 D8 a 632543 b 304 de 288 a8d 4434 b 73d 2576 BD
45692 b 007 F3 a2 f 7 C5 F5 aa 1d 99 ef 3866 af 26 a8e 8767 12ed 1 D4 C4 b 293 e 26 BC 0 a 1 DC 67 e 2477 15 caa6b
3028 f 946 1a3b 1533 EC 0 CB 47644 1465 f 10 D8 ad 47452 a 12db 060 1c5e 8 beda 686 DD 96 D2 ACD 59 ea 89 b 9 1
f 1834580c3f6d90898
B) decrypt c with e, as follows:
m=c**e%n:
c:\ Temp & gt； perl-mbi gint-e " $ x = Math::BigInt-& gt； bmodpow(0x 17b 287 be 4 18c 69 ECD 7c 39227 ab
68 1ac 422 FCC 84 bb 35 D8 a 632543 b 304 de 288 a8d 4434 b 73d 2576 BD 45692 b 007 F3 a2 f 7 C5 F5 aa 1d 99 ef 3
866 af 26 a8e 8767 12ed 1 D4 C4 b 293 e 26 BC 0 a 1 DC 67 e 2477 15 caa6b 3028 f 946 1a3b 1533 EC 0 CB 47644 14
65f 10 D8 ad 47452 a 12db 060 1c5 E8 beda 686 DD 96 D2 ACD 59 ea 89 b 9 1f 1834580 C3 F6 d 90898，0xE760A
3804 acde 1e8e 3d 7 DC 0 197 F9 cef 6282 ef 552 E8 cebb 7434 b 0 19 a9 d 87 a 3 106 DD 28 c 523 c 29954 C5 d
86b 36e 943080 e 49 19ca 8 ce 087 18c3b 0930867 a98f 635 EB 9 ea 9200 b 25906d 9 1b 80 a 4777324 e 66 aff
2 C4 D70 D8 b 1 c 69 c 50 a 9d 8 B4 b 7 a3 C9 ee 05 fff3 a 16 AFC 02373 1d 80634763 da 1d cabe 986 1 a 4789 BD 782 a
592D2B 1965，0x 328 c 74784 df 3 1 19c 526d 18098 e bebb 943 b 0032 b 599 CEE 13c C2 BCE 7 b 5 fcd 15f 90
b 66 EC 3 a 85 f 5005 dbdcded 9 BDF CB 3c 4 c 265 af 164 ad 55884d 8278 f 79 1 c 7 a 6 BF dad 55 EDB C4 f 0 17 f 9 CCF
1538 d4c 20 13433 b 383 b47 d 80 EC 74 b 5 1276 ca 05 b 5d 6346 b 9 ee 5 ad 2d 7 be 7 abfb 36 e 37 108 DD 6043894 1
d2ed 173 CCA 50 e 1 14705d 7 e2bc 5 1 195 1)； Print $ x-& gt；; as_hex "
0x 1 1 1 1 1 1 1 1 1 1 1 12222222222333333333
(I calculated it on my P4 1.6G machine for about 5 seconds.)
The e-decrypted m = 0x1111111/kloc-0.
Common implementation of RSA
RSA is simple and elegant, but its computing speed is slow. Generally, RSA is not directly used to encrypt all information.
The most common situation is to randomly generate a symmetric encryption key, then encrypt the information with a symmetric encryption algorithm, and then use it.
RSA encrypted the encryption key just now.
Finally, it should be noted that at present, it has been proved that n is less than 1024.
RSA with less than 1024 bits should not be used by yourself. It is best to use 2048-bit RSA.
-
JAVA source code of a simple RSA algorithm;
File name: RSA.java.
/*
* Founded on March 3, 2005.
*
* TODO To change the template of this makefile, go to.
* Window-Preferences-Java-Code Style-Code Template
*/
Import java.math.biginteger;
Import java.io.inputstream;
Import java.io.outputstream;
Import java.io.fileinputstream;
Import java.io.fileoutputstream;
import Java . io . filenotfoundexception；
Import java.io.ioexception;
Import java.io.filewriter;
Import java.io.filereader;
Import java.io.bufferedreader;
Import java.util.stringtokenizer;
/**
* @ Author Steve
*
* TODO To change the template for this generated type annotation, go to.
* Window-Preferences-Java-Code Style-Code Template
*/
Public class RSA {
/**
* Big integer. zero
*/
Private static final BigInteger ZERO = BigInteger. Zero;
/**
* Big integer. one
*/
Private static final BigInteger ONE = BigInteger. One;
/**
* pseudo BigInteger. two
*/
Private static final big integer two = new big integer ("2");
Private BigInteger myKey
Private BigInteger myMod
private int blockSize
Public RSA (BigInteger key, BigInteger n, int b) (
myKey = key
myMod = n；
block size = b；
}
Public void enco canal (string file name) (
Byte[] bytes = new byte [block size/8+1];
byte[]temp；
int tempLen
InputStream is = null.
FileWriter writer = null
Try {
Is = new file input stream (file name);
Writer = new file writer (file name+". enc”)；
}
catch(file not found exception e 1){
System.out.println ("file not found:"+filename);
}
catch (IOException e 1){
System.out.println ("File not found:"+filename+". enc”)；
}
/**
* Write the encoded message to the "file name". Technical control
*/
Try {
while ((tempLen = is.read(bytes， 1，block size/8))& gt； 0) {
for(int I = tempLen+ 1； I< bytes. Length; ++i) {
bytes[I]= 0；
}
writer . write(encoded decode(new big integer(bytes))+" ")；
}
}
catch (IOException e 1) {
System.out