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