What is the Use of RSA Algorithm Research Assignment - 6600 Words

What is the Use of RSA Algorithm Research Assignment (Math Problem Sample) Content: NameInstructor NameCourse NumberDateMATHEMATICS: RSA AlgorithmRSA AlgorithmUse 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 Euclids theory states thata(n)1 (mod 1) Where a and b are said to be relatively prime.With an arbitrary exponent m, it can be expressed as k1n+k2 for some values of k1and k2, thus the theorem implies that am=ak2(mod n)Eulers 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*dMe*dmod nM (mod n) where 0MFor 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 0M n, to represent the message to send, we would like to transform it to a cipher text, C by carrying out a modulo exponentiationC=M mod nLet 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 nM=Cdmod nSinceMedmod 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 RSAThis basis shown above will be used to decrypt and encrypt messages to ensure a private commun ication 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 As 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 od1 * They then, publish their public encryption key and keep their private decryption key secret.ExampleBoth e and d have been given from basis discussed above. T he modulus n has to be chosen.Choosing the ModulusThe 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 numbersFor 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 abov e equivalence is true becauseImplies for a particular integer kAdditionally, 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 its a prime number or not.Proof of the RSA algorithmWe use n which is a product of two primes p and q thusn=p*qm= (p-1) * (q-1)e proves that 1 e n and e an d m are coprime numbersd proves that d * e mod m =1m will satisfy 0 = m nc=m**e modulo nThusM== C**d modulo n is true * We need to prove that M== C**d modulo n is trueM** (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 pWhen M and P are comprime numbersM** (e*d) mod p= (1**k2)* M mod PThus M = PElseM == k*p must be true because P is a prime numberThusM mod p == 0M** (e*d) mod p == 0M** (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 operationM** (e*d) mod q == M mod q in proof b and because of modulus operationM** (e*d) M == k4*qM**(e*d) M==k5*n because of (2) and (4)M**(e*d) M == k5*n because n= p*qAnd because of modulus operation M mod n == M ** (e*d) mod n and for 0= M nAnd 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 Fermats 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=dIt 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 eThe 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 ab le 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 dAfter 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 Euclids algorithm to calculate d since (n) is equivalent to (p-1) * (q-1). It is of impo rtance 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 RSAWe 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- - - - - - - - - - 1bits 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 DecryptionA modular exponential is a type of an exponential that is performed on a mod...