What is the Use of RSA Algorithm Research Assignment (Math Problem Sample)

Name
Instructor Name
Course Number
Date
MATHEMATICS: RSA Algorithm
RSA Algorithm
Use of computers and internet has called for tight privacy protection as users have their sensitive information stored on networks and on computers. There have been many methods that have been developed but none beats the RSA algorithm used for encryption. For these reason, I have decided to find out how the algorithm encrypts and decrypts data and the mathematical concepts that makes it the hardest to crack.
The RSA is used to create a private communication channel through encryption that is done using mathematical principles. The Euclid’s theory states that
a∅(n)≡1 (mod 1) Where a and b are said to be relatively prime.
With an arbitrary exponent m, it can be expressed as k1∅n+k2 for some values of k1and k2, thus the theorem implies that am=ak2(mod n)
Euler’s theorem further implies that with two exponents, say, e and d such that one of them is a the multiplicative inverse of the other modulo Ø(n), we will have Me*d≡Me*dmod ∅n≡M (mod n) where 0≤M
For instance, take n to be 15 so p and q meaning that n= p*q and Ø(n)= (p-1) (q-1)
This property is very essential for the encryption and decryption of messages as it is shown below.
Let us take n as the modular arithmetic, an integer e which is a coprime to totient Ø(n), and d as the multiplicative inverse of e modulo Ø(n). Given a integer M, where 0≤M < n, to represent the message to send, we would like to transform it to a cipher text, C by carrying out a modulo exponentiation
C=M mod n
Let us take a block of cipher that we would like to encrypt 1024 bit block at a go. Now we can think oe every plain text block as an integer M with value of 0 ≤ M ≤ 21024-1.
From C we can get M as shownC=Me mod n
M=Cdmod n
Since
Medmod n=Med(mod Ø(n))≡M(mod n)
This creates the basis which the RSA algorithm uses in encryption and decryption of messages.
Implementing the Basis in RSA
This basis shown above will be used to decrypt and encrypt messages to ensure a private communication channel as discussed below.
Two people, A and B, want to communicate using a private channel. A is the recipient and B the sender. A will have a public key {e, n} which are integers and {d, n}, another pair of integers, as private key. B, on the other hand, wants to send a message M to A and therefore will use integers {e, n} which is A’s public key to create a cipher text C. A will have to use his private key {d, n} to decrypt C message M upon receiving it. In case M is too long, RSA will be used block cipher.
Both the sender and the receiver generate a public and a private key pair by
* Randomly selecting two large prime numbers: p and q
* They both compute the modulus n = p*q where Øn=(p-1)(q-1)
* They then select a random encryption key e where 1
* Solve the equation, e*d =1 mod Ø(n) to find decryption key d where o≤d≤1
* They then, publish their public encryption key and keep their private decryption key secret.
Example
Both e and d have been given from basis discussed above. The modulus n has to be chosen.
Choosing the Modulus
The modulus n is an important part of the RSA algorithm. This is because, the sender and the receiver must have them to enable either side to encrypt or decrypt a text. As indicated above, given d and e, then, the modulus n that is selected must satisfy the following conditions.
The above condition must be satisfied because the cypher text which is encrypted version of the initial message m. it should also be known that the encryption of the message integer M is performed by.
Research has indicated that, for the above condition to be met, n must be as a result of multiplying two prime numbers. This implies that:
N=p*q where p and q are prime numbers
For the above two numbers to be considered when determining the modulus n, each prime number or coprime numbers must possess the following qualities:
* If any 2 integers (p and q) are relatively prime to each other (coprimes),then the following is true for any 2 integers a and b:
{}{}
The above equivalence is true because
Implies for a particular integer k
Additionally, we also have implies this can be lead to for some. As a result, this can be written as and this proves the equivalence.
It should be known that the above equivalence is true if p and q have other common factors apart from 1.
* Apart from being coprimes, p and q should also be primes themselves. This means that if p and q are primes, then the totient of n can be decomposed into the totients of p and q.
To facilitate security of the cipher text, the two primes (p and q) are supposed to be very large. Apart from making the prime factors to be large, cipher security should be guaranteed by ensuring that n cannot be factorized by any factorizing algorithms.
The large size of the primes makes more difficult to determine the prime numbers than determining whether it’s a prime number or not.
Proof of the RSA algorithm
We use n which is a product of two primes p and q thus
n=p*q
m= (p-1) * (q-1)
e proves that 1> e > n and e and m are coprime numbers
d proves that d * e mod m =1
m will satisfy 0 => m> n
c=m**e modulo n
Thus
M== C**d modulo n is true
* We need to prove that M== C**d modulo n is true
M** (e*d) mod p
=m** (k1*m+1) mod p because d*e mod m = 1 and factoring 1 M out = (M** (k1*m)) * M mod p. Because m= (p-1) * (q-1) which is = (M** (k1* (q-1) * (p-1)))*M mod p and then set k2= k1 * (q-1) which is = (M** (k2* (p-1)))*M mod p then
= ((M** (p-1) mod p) **k2)* M mod p
When M and P are comprime numbers
M** (e*d) mod p
= (1**k2)* M mod P
Thus M = P
Else
M == k*p must be true because P is a prime number
Thus
M mod p == 0
M** (e*d) mod p == 0
M** (e*d) mod p ==M mod P
* M** (e*d) mod q == M can be proved as in the above steps
* M==C**d mod n is true in that:
In proof M** (e*d) – M == k3*p and through modulus operation
M** (e*d) mod q == M mod q in proof b and because of modulus operation
M** (e*d) – M == k4*q
M**(e*d) – M==k5*n because of (2) and (4)
M**(e*d) – M == k5*n because n= p*q
And because of modulus operation M mod n == M** (e*d) mod n and for 0=< M < n
And through moving mod n M== (M**e mod n) **d mod n and because c= M** mod n, M== c**d mod n it is through the use of Fermat’s theorem that RSA is also proofed here which states that a**p-a is an integer and multiple of p can be an integer if p is a prime number.
Computational steps for key generation in RSA
1 Start by choosing too large prime numbers p and q
2 Calculate n= p*q
3 Compute Ø(n)= p(p-1)*q(q-1)
4 Selecting a public exponent eƸ {1,2...,Ø(n)-1} such that gcd(e,Øn) )=1
5 Find the private key d in that d =e-1 mod Ø (n)
6 Return K public= (n,e), kprivate=d
It is non-trivial when choosing two prime numbers p and q while gcd(e,Øn) )=1 ensures that e has an inverse and that there is always a private key d.
Choosing a Value for the Public Exponent e
The mathematical requirement of e satisfies that gcd(e, Ø (n))=e since e might have no multiplicative inverse mod Ø(n). The two requirements of gcd(e, Ø(p))=1 and gcd(e, Ø(q))=1 are equivalent with n=p*q. To be able to compute easily it is necessary to choose a value for e that is prime and has few bits that are equal to 1 that can be multiplied fast and easily and cryptographically safe and secure for example values for e are 3,17 and 65537=(216+1) though small values for e are mostly considered cryptographically insecure. It is therefore necessary to double check that the values of e satisfy of gcd(e, p-1)=1 and gcd(e, q-1)=1 since it is required that e to be a coprime of Ø(n) that is coprime of p-1 and q-1 separately. After making a choice for the encryption integer e, it is important to satisfy that e would also be coprime to the totients Ø(p) and Ø(q).
Calculating the private exponent d
After a value has been derived for the exponent e, Exponent d is calculated from e and modulus n.
Modular inversion is used by calculating using e-1mod Ø (n). d is the inverse of e modulo Ø(n) and thus it is possible to use Euclid’s algorithm to calculate d since Ø(n) is equivalent to (p-1) * (q-1). It is of importance to keep Ø(n), p and q values as a secret because knowing either would reveal the other. This is because by multiplying (p-1) with (q-1) you can get Ø(n) and if you Ø(n) and n you can calculate p and q .
Toy example illustrating how to set n, e, and d for a block cipher application of RSA
We are required to use small size bits such as 8bits since the modulus size is set to 16bits because the message integer M must be smaller than the modulus n since the block size cannot be equal with the modulus. With 8bits padding scheme is used here to fill up the rest of the bits. Padding makes the cipher more resistant to vulnerabilities. Recalling that n is a product of two prime numbers p and q then we allocate 8bits to each prime number so that they can be the same so that it is possible to find the prime suitable for 8bit representation. Assuming that the 8bit for p with the first and last bit are set and also that is true for q.
bits of p : 11- - - - - - - - - - 1
bits of q: 11- - - - - - - - - - 1
“-” stands for the bit that is yet to be determined. Through this it is easier to verify that an 8bit has a decimal value of 193.
Modular Exponentiation for Encryption and Decryption
A modular exponential is a type of an exponential that is performed on a mod...