RSA Algorithm: D e D Ed

RSA Algorithm
Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977
Used for both public key encryption and digital signatures
Plain text is encrypted in blocks, each block having a binary value less
than some number n.
Block size <= log2(n); ,the block size is i bits, where 2i < n<= 2i+1
C = Me mod n
M = Cd mod n = (Me)d mod n = Med mod n
public key of KU = {e, n}
private key of KR = {d, n}
Requirements
•It is possible to find values of e, d, n such that Med = M mod n for all
M < n.
•It is relatively easy to calculate mod Me and Cd for all values of
M < n.
•It is infeasible to determine d given e and n.
Med = M mod n
According to Euler’s theorem

Given two prime numbers p & q and two integers n and m such that n = pq
and 0 < m < n
Arbitrary integer k
mkΦ(n)+1=mk(p-1)(q-1)+1=m mod n
p,q prime
Φ(pq) = (p-1)(q-1)
The preceding relationship holds if e and d are multiplicative inverses modulo
Φ(n), where Φ(n) is the Euler totient function.
ed = k Φ(n) + 1
This is equivalent to saying
ed =1 mod Φ(n)
d =e-1 mod Φ(n)
That is, e and d are multiplicative inverses mod Φ(n).
Equivalently, gcd(Φ(n),d) = 1.
Ingredients of RSA
p,q, two prime numbers (private, chosen)

n = pq (public, calculated)
e, with gcd(Φ(n),e) = 1;1 < e < Φ(n) (public, chosen)
d =e-1(mod Φ(n)) (private, calculated)
The private key consists of {d, n} and the public key consists of {e, n}.
Suppose that user A has published its public key and that user B
wishes to send the message M to A. Then B calculates C = Me mod n
and transmits C. On receipt of this ciphertext, user A decrypts by
calculating M = Cd mod n.
• Select two prime numbers, p = 17 and q = 11.
• Calculate n = pq = 17 x 11 = 187.
• Calculate Φ(n) = (p - 1)(q - 1) = 16 x 10 = 160.
• Select e such that e is relatively prime to Φ(n) = 160 and less than
Φ(n) we choose e = 7.
• Determine d such that de = 1 (mod 160) and d < 160. The correct
value is d = 23, because 23 x 7 = 161 = 160 + 1; d can be calculated
using the extended Euclid's algorithm
RSA is usch slower than DES & Other Symmetric Cryptosystems
The Security of RSA
Four possible approaches to attacking the RSA algorithm:
Brute force: This involves trying all possible private keys.
Mathematical attacks: There are several approaches, all equivalent in

effort to factoring the product of two primes.
Timing attacks: These depend on the running time of the decryption

algorithm.
Chosen ciphertext attacks: This type of attack exploits properties of the

RSA algorithm.
The defense against the brute-force approach is the same for RSA as for
other cryptosystems, use a large key space. Thus, the larger the number of
bits in d, the better.
The Factoring Problem
• Three approaches to attacking RSA mathematically

• Factor n into its two prime factors.
• Enables calculation of f(n) = (p - 1) x (q - 1), which, in turn, enables
determination of d e1 (mod f(n)).
• Determine f(n) directly, enables determination of d e1 (mod f(n)).
• Determine d directly, without first determining f(n).
Example Illustration
The resulting keys are public key PU = {7,187} and private key
PR = {23,187}.
Plain text input of M = 88.
For encryption, calculate C = 887 mod 187.

887 mod 187 = [(884 mod 187) x (882 mod 187) x (881 mod
187)] mod 187
881 mod 187 = 88
882 mod 187 = 7744 mod 187 = 77
884 mod 187 = 59,969,536 mod 187 = 132
887 mod 187 = (88 x 77 x 132) mod 187 = 894,432 mod 187
= 11
For decryption, we calculate M = 1123 mod 187:
1123 mod 187 = [(111 mod 187) x (112 mod 187) x (114 mod
187) x (118 mod 187) x (118 mod 187)] mod 187
111 mod 187 = 11
112 mod 187 = 121
114 mod 187 = 14,641 mod 187 = 55
118 mod 187 = 214,358,881 mod 187 = 33
1123 mod 187 = (11 x 121 x 55 x 33 x 33) mod 187 =
79,720,245 mod 187 = 88
3. PUBLIC KEY AUTHORITY
4. PUBLIC CERTIFICATE
Digital Signatures
Message authentication protects two parties who exchange messages from any
third party.
Scenario
An electronic funds transfer takes place, and the receiver increases the amount of
funds transferred and claims that the larger amount had arrived from the sender.
Not complete trust between sender and receiver
DS have the following properties:

It must verify the author and the date and time of the signature.
It must to authenticate the contents at the time of the signature.
It must be verifiable by third parties, to resolve disputes.

On the basis of these properties, we can formulate the following
requirements for a digital signature:
•The signature must be a bit pattern that depends on the message being
signed.
•The signature must use some information unique to the sender, to

prevent both forgery and denial.
•It must be relatively easy to produce the digital signature.
•It must be relatively easy to recognize and verify the digital signature.
•It must be computationally infeasible to forge a digital signature, either by

constructing a new message for an existing digital signature or by
constructing a fraudulent digital signature for a given message.
•It must be practical to retain a copy of the digital signature in storage.

A secure hash function, embedded in a scheme satisfies these
requirements.
Direct Digital Signature
The direct digital signature involves only the communicating parties
(source, destination).
A digital signature may be formed by encrypting the entire message with
the sender's private key or by encrypting a hash code of the message
with the sender's private key.
Arbitrated Digital Signature

Every signed message from a sender X to a receiver Y goes first to an arbiter A,
who subjects the message and its signature to a number of tests to check its
origin and content.
The message is then dated and sent to Y with an indication that it has been
verified to the satisfaction of the arbiter.
Key Generation in RSA
• Determining two prime numbers, p and q
• Selecting either e or d and calculating the other
One of the more efficient and popular algorithms, the Miller-Rabin
algorithm
Procedure for testing whether a given integer n is prime
Perform some calculation that involves n and a randomly chosen

integer a.
If n "fails" the test, then n is not prime.
If n "passes" the test, then n may be prime or nonprime. If n passes

many such tests with many different randomly chosen values for a,
then we can have high confidence that n is, in fact, prime.
In summary, the procedure for picking a prime number is as follows.
1. Pick an odd integer n at random (e.g., using a pseudorandom number
generator).
2. Pick an integer a < n at random.
3. Perform the probabilistic primality test, such as Miller-Rabin, with a as a

parameter. If n fails the test, reject the value n and go to step 1.
4. If n has passed a sufficient number of tests, accept n; otherwise, go to step 2.

Issues in RSA
RSA Factoring Challenge - practical difficulty of factoring large integers

and cracking RSA keys used in cryptography
The smallest , a 100 decimal digit number called RSA-100 was factored by
April 1, 1991
A primary application is for choosing the key length of the RSA public-key
encryption scheme.
The RSA numbers were generated on a computer with no network

connection of any kind. The computer's hard drive was subsequently
destroyed so that no record would exist, anywhere, of the solution to the
factoring challenge.
The first RSA numbers generated, from RSA-100 to RSA-500, were labeled
according to their number of decimal digits
Key Management
DH Computation Issues
Diffie–Hellman key exchange (D–H) is a cryptographic protocol that allows

two parties that have no prior knowledge of each other to jointly establish a
shared secret key over an insecure communications channel. This key can
then be used to encrypt subsequent communications using a symmetric key
cipher.
Alice and Bob agree to use a prime number p=23 and base g=5.
Alice chooses a secret integer a=6, then sends Bob A = ga mod p
A = 56 mod 23 = 8.
Bob chooses a secret integer b=15, then sends Alice B = gb mod p
B = 515 mod 23 = 19.
Alice computes s = B a mod p
196 mod 23 = 2.
Bob computes s = A b mod p
815 mod 23 = 2.
Elliptic curve cryptography (ECC) is an approach to public-key cryptography
based on the algebraic structure of elliptic curves over finite fields.
Elliptic curves are also used in several integer factorization algorithms that have
applications in cryptography
An elliptic curve is a plane curve which consists of the points satisfying the equation
y^2 = x^3 + ax + b
Several RSA-based protocols have been adapted to elliptic curves, replacing the
group Zpq with an elliptic curve:
* The Elliptic Curve Diffie-Hellman key agreement scheme is based on the Diffie-
Hellman scheme,
* The Elliptic Curve Digital Signature Algorithm is based on the Digital Signature
Algorithm,
* The ECMQV key agreement scheme is based on the MQV key agreement
scheme.
HASH Function in Cryptography
A hash function H is a transformation that takes a variable-size input m and
returns a fixed-size string, which is called the hash value h (that is, h =
H(m)).
Hash functions with just this property have a variety of general

computational uses, but when employed in cryptography the hash functions
are usually chosen to have some additional properties.
The basic requirements for a cryptographic hash function are:
* the input can be of any length,

* the output has a fixed length,
* H(x) is relatively easy to compute for any given x ,
* H(x) is one-way,
* H(x) is collision-free.
Used in digital signatures, message authentication codes (MACs). They can also
be used as ordinary hash functions, to index data in hash tables; as fingerprints,
to detect duplicate data or uniquely identify files
A related application is password verification. Passwords are usually not stored in

cleartext, instead in digest form. To authenticate a user, the password presented
by the user is hashed and compared with the stored hash. This is sometimes
referred to as one-way encryption.
MD5 algorithm
In cryptography, MD5 (Message-Digest algorithm 5) is a widely used
cryptographic hash function with a 128-bit hash value. commonly used to check
the integrity of files.
MD5 processes a variable-length message into a fixed-length output of 128 bits.
The input message is broken up into chunks of 512-bit blocks (sixteen 32-bit little
endian integers)
Chinese Remainder Theorem
There are certain things whose number is unknown.
Repeatedly divided by 3, the remainder is 2;
by 5 the remainder is 3;
and by 7 the remainder is 2.
What will be the number?
Suppose n1, n2, …, nk are positive integers which are pairwise coprime.
Then, for any given integers a1,a2, …, ak, there exists an integer x solving
the system of simultaneous congruences
In mathematical way the problems can be stated as finding n, given its
remainders
of division by several numbers m1,m2,...,mk:
n = n1 (mod m1)
n = n2 (mod m2)
...
n = nk (mod mk)
Extended Euclidean algorithm is an extension to the Euclidean algorithm for
finding the greatest common divisor (GCD) of integers a and b

RSA Algorithm: D e D Ed

Uploaded by

Copyright:

Available Formats

RSA Algorithm: D e D Ed

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

RSA Algorithm: D e D Ed

Uploaded by

Copyright:

Available Formats

RSA Algorithm

According to Euler’s theorem

p,q, two prime numbers (private, chosen)

Brute force: This involves trying all possible private keys.

Mathematical attacks: There are several approaches, all equivalent in

Timing attacks: These depend on the running time of the decryption

Chosen ciphertext attacks: This type of attack exploits properties of the

• Three approaches to attacking RSA mathematically

Plain text input of M = 88.

For encryption, calculate C = 887 mod 187.

Not complete trust between sender and receiver

DS have the following properties:

It must to authenticate the contents at the time of the signature.

It must be verifiable by third parties, to resolve disputes.

•The signature must use some information unique to the sender, to

•It must be relatively easy to produce the digital signature.

•It must be computationally infeasible to forge a digital signature, either by

•It must be practical to retain a copy of the digital signature in storage.

Arbitrated Digital Signature

Procedure for testing whether a given integer n is prime

Perform some calculation that involves n and a randomly chosen

If n "passes" the test, then n may be prime or nonprime. If n passes

2. Pick an integer a < n at random.

3. Perform the probabilistic primality test, such as Miller-Rabin, with a as a

4. If n has passed a sufficient number of tests, accept n; otherwise, go to step 2.

RSA Factoring Challenge - practical difficulty of factoring large integers

The RSA numbers were generated on a computer with no network

Diffie–Hellman key exchange (D–H) is a cryptographic protocol that allows

Hash functions with just this property have a variety of general

The basic requirements for a cryptographic hash function are:

* the input can be of any length,

A related application is password verification. Passwords are usually not stored in

You might also like