Essay Available:

You are here: Home → Math Problem → Mathematics & Economics

Pages:

12 pages/≈6600 words

Sources:

11 Sources

Level:

APA

Subject:

Mathematics & Economics

Type:

Math Problem

Language:

English (U.S.)

Document:

MS Word

Date:

Total cost:

$ 86.4

Topic:

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

Instructions:

What is the use of 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.

Content:

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

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

Get the Whole Paper!

Not exactly what you need?

Do you need a custom essay? Order right now:

### Other Topics:

- Area Under a Normal Distribution Curve Research AssignmentDescription: Take a position on whether or not the total area under a normal distribution is inﬁnite. Provide an example to support your response....1 page/≈275 words| 1 Source | APA | Mathematics & Economics | Math Problem |
- Break Even and Shut Down AnalysisDescription: Break Even and Shut Down Analysis Mathematics and Economics Math Problem...2 pages/≈550 words| APA | Mathematics & Economics | Math Problem |
- MAT101 Case 4 Answer TemplateDescription: What are the 3 methods for solving systems of equations? Which one do you prefer and why?...20 pages/≈5500 words| No Sources | APA | Mathematics & Economics | Math Problem |