RSA Algorithm - An Overview
BY : Darshana Chaturvedi
INTRODUCTION
RSA ALGORITHM
EXAMPLES
RSA IS EFFECTIVE
FERMAT’S LITTLE THEOREM
EUCLID’S ALGORITHM
REFERENCES
Cryptography
Ancient art.
Science of writing in secret code.
Art of protecting information by encrypting it into an
unreadable format, called cipher text which can be
decrypted into the plain text using a secret key.
Uses
Email – messages
Credit card information
Corporate data
Types
Symmetric-key systems(uses a single key)
Public-key systems introduced in 1970’s(uses a public
key known to everyone and a private key that only the
receiver of the messages uses)
Previously both senders and receivers implemented
the algorithms by hand but with the advent of
computers, things changed
.
Simplest cryptographic systems
Algorithms for both encryption and decryption are
fixed and known to everyone.
There are two inputs, the text to be encoded or
decoded and a key.
Symmetric key encryption
No message can be sent unless there has been some
prior agreement on a key.
Even if there is an agreement, if the same key is used
over an extended period of time, an eavesdropper may
be able to infer the key and break the code.
New keys must be transmitted between the senders
and receivers to avoid code breaking.
The most widely used public key system is the RSA
algorithm.
RSA algorithm [Rivest , Shamir and Adleman] in 1978
We assume that Bob and Alice wish to exchange
secure messages and that Eve is attempting to
eavesdrop.
Assume that Alice wants to send a message to Bob.
Then
Bob chooses a private key known only to him. Bob
exploits a function
f
to compute his public key,
public = f(private).
Bob publishes
public key.
Alice exploits Bob’s public key to compute
ciphertext= encrypt(plaintext, public)
and she
sends
ciphertext
to Bob.
Bob
exploits his private key to compute
plaintext=
decrypt(ciphertext, private).
In order for this last
step to work, encrypt and decrypt must be
designed so that one is the inverse of the other.
If there exist efficient algorithm for performing all four
of the steps, then Bob and Alice will be able to
exchange messages.
We assume that Eve knows the algorithm
encrypt
and
decrypt
. So she could easily eavesdrop if she could
infer Bob’s private key from his public one or if she
could compute
decrypt
without knowing Bob’s private
key.
RSA algorithm uses the mathematical properties of
modular arithmetic and the computational properties
of prime numbers to ensure that Bob and Alice can
perform their tasks efficiently but Eve cannot.
Alice uses the RSA algorithm to send a message to
Bob as follows.
Bob constructs his public and private keys
Bob chooses two large prime numbers p and q. From
them, he computes
n=p*q.
Bob, finds a value e such that 1 < e < p.q and gcd(e,(p-
1)(q-1))=1. (in other words, he finds an e such that e
and (p-1).(q-1) are relatively prime).
Bob computes a value d such that d.e(mod(p-1).(q-1))=
1. In RSA terminology, this value d, rather than the
original numbers p and q, is referred to as Bob’s
private key.
Bob publishes (n,e) as his public key.
Alice breaks her message plaintext into segments
such that no segment corresponds to a binary number
that is larger than n. Then, for each plaintext segment,
Alice computes
ciphertext = plaintext
e
(mod n).
Then
she sends
ciphertext
to Bob.
Bob recreates Alice’s original message by computing
plaintext = ciphertext
d
(mod n)
.
We can illustrate the RSA algorithm with a simple
message from Alice to Bob.
Bob is expecting to receive messages. So he
constructs his keys as follows:
He chooses two prime numbers, p=3 and q=11. He
computes n=p*q=33.
He finds an e such that 1<e<33 and gcd (e,20) =
1. Then e he selects is 7.
Then he finds the value of d such that d*e(mod(p-
1)(q-1)) = 1. Hence d is 3 as 3*7(mod 20) = 1.So,3
is the Bob’s private key.
Bob publishes (33,7) as his public key.
Alice wishes to send the simple message 2. So Alice
computes 2
7
(MOD 33) = 29.
Alice sends Bob the message 29.
Bob uses his private key to recreate Alice’s original
message by computing 29
3
(MOD 33) = 2.
Hence, Bob decrypts the message and read it.
Sending message from Alice to Bob
Bob is expecting to receive messages. So he
constructs his keys as follows:
He chooses two prime numbers, p=19 and q=31.
He computes n=p*q=589.
He finds an e that has no common divisors with
18*30=540. The e he selects is 49.
He finds a value d =1069. Notice that 1069*49
=52381. Bob needs to assure that the remainder,
when 52381 is divided by 540, is 1. And it is
:52381=540*97+1. Bob’s private key is now
1069.
Bob publishes (589,49) as his public key.
Alice wishes to send the simple message “A”. The
ASCII code for A is 65. So Alice computes
65
49
(mod589). She does without actually computing
65
49
. Instead, she exploits the following two facts:
n
i+j
=n
i
*n
j
(n*m)(mod k) =(n(mod k)*m(mod k))(mod k)
Combining these, we have:
n
i+j
(mod k) = (n
i
(mod k)*n
j
(mod k))(mod k)
So, to compute 65
49
,first observe that 49 can be
expressed in binary as 110001. So 49 = 1+16+32
Thus, 65
49
= 65
1+16+32
.The following table lists the
required powers 65:
65
1
(mod589)=65
65
2
(mod589)=4225(mod589)=102
65
4
(mod589)=102
2
(mod589)=10404(mod589)=391
65
8
(mod589)=391
2
(mod589)=152881(mod589)=330
65
16
(mod589)=330
2
(mod589)=108900(mod589)=524
65
32
(mod589)=524
2
(mod589)=274576(mod589)=102
So we have:65
49
(mod589)
= 65
1+16+32
(mod589)
=(65
1
*65
16
*65
32
)(mod589)
=((65
1
(mod589))*(65
16
(mod589))*(65
32
(mod589)))(mo
d589)
=(65*524*102)(mod589)
=((34060(mod589))*102)(mod589)
=(487*102)(mod589)
=198
Alice sends Bob the message 198.
Bob uses his private key(1069) to recreate Alice’s
message by computing 198
1069
(mod589). Using the
same process Alice used, he does this efficiently and
retrieves the message 65.
The function encrypt and decrypt are inverse of each
other and it is proved using euler’s generalization of
Fermat’s Little theorem.
Bob can choose primes efficiently using the following
algorithm.
Randomly choose two large numbers as
candidates.
Check the candidates to see if they are prime. This
can be done efficiently using a randomized
algorithm, Fermat’s Little theorem.
If p is prime , then, for any integer a, if gcd(a,p) = 1, a
p-
1
≡ 1 (mod p).
Where , x ≡ y (mod p) means x and y have the same
remainder when divided by p.
Example : p = 5 and a = 3, then ,
3
(5-1)
= 81 ≡ 1 (mod 5) which is true.
So, 5 passes the Fermat test at a = 3.
If p fails the Fermat’s test at ‘a’ then we will say that
‘a’ is a Fermat witness that ‘p’ is composite.
The theorem tells us that if ‘p’ is prime ,then it must
pass the Fermat test at every appropriately chosen
value of a.
QUESTION : If p passes the Fermat test at some value
of ‘a’, do we know that p is prime?
ANSWER : No
Conclusion : If p is composite and yet it passes the
Fermat test at ‘a’, we will say that ‘a’ is a Fermat Liar
that p is prime.
Randomly choose values for ‘a’ looking for a witness
that p is composite.
Note : Consider the values which are less then p only.
So, if p is prime then gcd(a,p) is always 1.
No need to evaluate gcd anymore in our algorithm.
If we fail to find a witness that shows that p is
composite, we will report that p is prime.
As liars exists, increase the likelihood of finding such a
witness , if one exists, by increasing the witnesses that
we test.
Algorithm :
Input : A value to be tested and the possible witnesses
to be checked.
Output : Composite or Probably Prime number.
simpleFermat(p:integer,k:integer) =
Do k times.
- Select a in range 2 to p-1
- If a
p-1
≡ 1 is not true , return Composite
If all tests passed then return Probably Prime.
Some composite numbers pass the test at all
values of ‘a’ and are called ‘Carmichael
numbers’.
Every value of ‘a’ is a Fermat liar for every
Carmichael number, so no value of k will
enable simpleFermat to realize that a
Carmichael number is not prime.
Successive division of 2 numbers followed by the
resulting remainder divided into the divisor of each
division until the remainder is equal to zero. Then the
remainder of the previous division is the gcd.
Example :
Divident = Quotient * Divisor + Remainder
If a = 1071 and b = 462, gcd (1071,462) is :
Then, 1071 = 2 *
462
+
147
462 = 3 *
147
+
21
147 = 7 * 21 +
0
Stop, as remainder is 0.
gcd (1071,462) = 21
Automata, Computability, and Complexity| Theory and
Applications by Elaine Rich.
En.wikipedia.org
Presentation from the previous class
THANK YOU
Cryptography is the science of writing in secret code to protect information. The RSA algorithm, introduced by Rivest, Shamir, and Adleman in 1978, is a popular public key system. It involves the exchange of secure messages between senders and receivers to avoid code breaking. This algorithm uses both public and private keys for encryption and decryption to ensure data security.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
RSA ALGORITHM BY : Darshana Chaturvedi
OUTLINE INTRODUCTION RSA ALGORITHM EXAMPLES RSA IS EFFECTIVE FERMAT S LITTLE THEOREM EUCLID S ALGORITHM REFERENCES
INTRODUCTION Cryptography Ancient art. Science of writing in secret code. Art of protecting information by encrypting it into an unreadable format, called cipher text which can be decrypted into the plain text using a secret key. Uses Email messages Credit card information Corporate data
CONT.. Types Symmetric-key systems(uses a single key) Public-key systems introduced in 1970 s(uses a public key known to everyone and a private key that only the receiver of the messages uses) Previously both senders and receivers implemented the algorithms by hand but with the advent of computers, things changed.
CONT.. Simplest cryptographic systems Algorithms for both encryption and decryption are fixed and known to everyone. There are two inputs, the text to be encoded or decoded and a key.
CONT.. Symmetric key encryption No message can be sent unless there has been some prior agreement on a key. Even if there is an agreement, if the same key is used over an extended period of time, an eavesdropper may be able to infer the key and break the code.
RSA ALGORITHM New keys must be transmitted between the senders and receivers to avoid code breaking. The most widely used public key system is the RSA algorithm. RSA algorithm [Rivest , Shamir and Adleman] in 1978 We assume that Bob and Alice wish to exchange secure messages and that Eve is attempting to eavesdrop.
CONT.. Assume that Alice wants to send a message to Bob. Then Bob chooses a private key known only to him. Bob exploits a function f to compute his public key, public = f(private). Bob publishes public key. Alice exploits Bob s public key to compute ciphertext= encrypt(plaintext, public) and she sends ciphertext to Bob.
CONT.. Bob exploits his private key to compute plaintext= decrypt(ciphertext, private). In order for this last step to work, encrypt and decrypt must be designed so that one is the inverse of the other.
CONT.. If there exist efficient algorithm for performing all four of the steps, then Bob and Alice will be able to exchange messages. We assume that Eve knows the algorithm encrypt and decrypt . So she could easily eavesdrop if she could infer Bob s private key from his public one or if she could compute decrypt without knowing Bob s private key.
CONT.. RSA algorithm uses the mathematical properties of modular arithmetic and the computational properties of prime numbers to ensure that Bob and Alice can perform their tasks efficiently but Eve cannot.
STEPS Alice uses the RSA algorithm to send a message to Bob as follows. Bob constructs his public and private keys Bob chooses two large prime numbers p and q. From them, he computes n=p*q. Bob, finds a value e such that 1 < e < p.q and gcd(e,(p- 1)(q-1))=1. (in other words, he finds an e such that e and (p-1).(q-1) are relatively prime). Bob computes a value d such that d.e(mod(p-1).(q-1))= 1. In RSA terminology, this value d, rather than the original numbers p and q, is referred to as Bob s private key.
CONT.. Bob publishes (n,e) as his public key. Alice breaks her message plaintext into segments such that no segment corresponds to a binary number that is larger than n. Then, for each plaintext segment, Alice computes ciphertext = plaintexte(mod n). Then she sends ciphertext to Bob. Bob recreates Alice s original message by computing plaintext = ciphertextd(mod n).
EXAMPLE 1 We can illustrate the RSA algorithm with a simple message from Alice to Bob. Bob is expecting to receive messages. So he constructs his keys as follows: He chooses two prime numbers, p=3 and q=11. He computes n=p*q=33. He finds an e such that 1<e<33 and gcd (e,20) = 1. Then e he selects is 7.
CONT.. Then he finds the value of d such that d*e(mod(p- 1)(q-1)) = 1. Hence d is 3 as 3*7(mod 20) = 1.So,3 is the Bob s private key. Bob publishes (33,7) as his public key. Alice wishes to send the simple message 2. So Alice computes 27 (MOD 33) = 29. Alice sends Bob the message 29. Bob uses his private key to recreate Alice s original message by computing 293 (MOD 33) = 2. Hence, Bob decrypts the message and read it.
EXAMPLE 2 Sending message from Alice to Bob Bob is expecting to receive messages. So he constructs his keys as follows: He chooses two prime numbers, p=19 and q=31. He computes n=p*q=589. He finds an e that has no common divisors with 18*30=540. The e he selects is 49.
CONT.. He finds a value d =1069. Notice that 1069*49 =52381. Bob needs to assure that the remainder, when 52381 is divided by 540, is 1. And it is :52381=540*97+1. Bob s private key is now 1069. Bob publishes (589,49) as his public key.
CONT.. Alice wishes to send the simple message A . The ASCII code for A is 65. So Alice computes 6549(mod589). She does without actually computing 6549. Instead, she exploits the following two facts: ni+j=ni*nj (n*m)(mod k) =(n(mod k)*m(mod k))(mod k) Combining these, we have: ni+j(mod k) = (ni(mod k)*nj(mod k))(mod k)
CONT.. So, to compute 6549,first observe that 49 can be expressed in binary as 110001. So 49 = 1+16+32 Thus, 6549 = 651+16+32.The following table lists the required powers 65: 651(mod589)=65 652(mod589)=4225(mod589)=102 654(mod589)=1022(mod589)=10404(mod589)=391
CONT.. 658(mod589)=3912(mod589)=152881(mod589)=330 6516(mod589)=3302(mod589)=108900(mod589)=524 6532(mod589)=5242(mod589)=274576(mod589)=102 So we have:6549(mod589) = 651+16+32(mod589) =(651*6516*6532)(mod589) =((651(mod589))*(6516(mod589))*(6532(mod589)))(mo d589)
CONT.. =(65*524*102)(mod589) =((34060(mod589))*102)(mod589) =(487*102)(mod589) =198 Alice sends Bob the message 198. Bob uses his private key(1069) to recreate Alice s message by computing 1981069(mod589). Using the same process Alice used, he does this efficiently and retrieves the message 65.
RSA IS EFFECTIVE The function encrypt and decrypt are inverse of each other and it is proved using euler s generalization of Fermat s Little theorem. Bob can choose primes efficiently using the following algorithm. Randomly choose two candidates. Check the candidates to see if they are prime. This can be done efficiently using a randomized algorithm, Fermat s Little theorem. large numbers as
FERMATS LITTLE THEOREM If p is prime , then, for any integer a, if gcd(a,p) = 1, ap- 1 1 (mod p). Where , x y (mod p) means x and y have the same remainder when divided by p. Example : p = 5 and a = 3, then , 3 (5-1)= 81 1 (mod 5) which is true. So, 5 passes the Fermat test at a = 3. If p fails the Fermat s test at a then we will say that a is a Fermat witness that p is composite.
CONT.. The theorem tells us that if p is prime ,then it must pass the Fermat test at every appropriately chosen value of a. QUESTION : If p passes the Fermat test at some value of a , do we know that p is prime? ANSWER : No Conclusion : If p is composite and yet it passes the Fermat test at a , we will say that a is a Fermat Liar that p is prime.
CONT.. Randomly choose values for a looking for a witness that p is composite. Note : Consider the values which are less then p only. So, if p is prime then gcd(a,p) is always 1. No need to evaluate gcd anymore in our algorithm. If we fail to find a witness that shows that p is composite, we will report that p is prime. As liars exists, increase the likelihood of finding such a witness , if one exists, by increasing the witnesses that we test.
CONT.. Algorithm : Input : A value to be tested and the possible witnesses to be checked. Output : Composite or Probably Prime number. simpleFermat(p:integer,k:integer) = Do k times. - Select a in range 2 to p-1 - If ap-1 1 is not true , return Composite If all tests passed then return Probably Prime.
CONT.. Some composite numbers pass the test at all values of a and are called Carmichael numbers . Every value of a is a Fermat liar for every Carmichael number, so no value of k will enable simpleFermat to realize that a Carmichael number is not prime.
EUCLIDS ALGORITHM Successive division of 2 numbers followed by the resulting remainder divided into the divisor of each division until the remainder is equal to zero. Then the remainder of the previous division is the gcd. Example : Divident = Quotient * Divisor + Remainder If a = 1071 and b = 462, gcd (1071,462) is : Then, 1071 = 2 * 462 + 147 462 = 3 * 147 + 21 147 = 7 * 21 + 0 Stop, as remainder is 0. gcd (1071,462) = 21
REFERENCES Automata, Computability, and Complexity| Theory and Applications by Elaine Rich. En.wikipedia.org Presentation from the previous class
