Understanding Public Key Cryptosystems in RSA Encryption
Public key cryptosystems, like RSA, use two keys for encryption and decryption, with one key made public and the other kept secret. This asymmetric system allows secure communication, where the encryption key (E) is used to encrypt messages into ciphertext (C), which can only be decrypted back to the original message (M) using the secret decryption key (D). The underlying mathematics involve principles like modulus (n), prime numbers (p, q), and the Euler function. The RSA system's security relies on the difficulty of factoring large numbers, making it a key element in modern cryptography.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Public Key Cryptosystems: These public key cryptosystems have with two keys, one for encryption which is made public and the other for decryption which is kept secret. These systems are sometimes called asymmetric systems since the key used for encryption is different from the key used for decryption. Two very well known of such systems will be presented:
A]-RSA public key system: Each user places in a public file an encryption key E and keeps a secret key D. By knowing E, the 3rdparty cannot deduce D so easy. The RSA was developed by Rivest, Shamer and Adelman. Properties: 1- Deciphering the enciphered form of the message M will give again M, i.e,: D(E(M))=M. (Note also that E(D(M))=M) 2- The 3rdparty cannot deduce D from E so easily. 3- Both D & E are easy to compute. Encryption: Block the message into a series of blocks. 2- Represent blocks by integers between 0 & n-1, call it M. 3- The ciphertext is C= Memod n
Decryption: The message M can be easily obtained by: M= Cdmod n Underlying Mathematics: 1- n: modulus, which is public. This n depends on the size of the binary block that generates the messages M, for example if blocks of say m bits, then n>2m-1. 2- Let p and q be two large prime, +ve, random and private (secret) 3- Let e be the encryption key, integer, +ve, random, public. And Let d be the decryption key, integer, +ve, secret. The relation between e & d is: e*d=1 mod (?(?))
Where ? ? = Euler fn= (p-1)*(q-1) if both p &q are primes. To prove that the deciphering works correctly and gives M from C, then: D((E(M))=(E(M))d = Me*dmod n = (?k ? ? +1)??? ? = M mod n =M since M< ? Where k is an integer Notes:1- In any public key cryptosystem, there must be a so called one way function . This function is easy to be found in one direction, but it is very very difficult to be found in the inverse direction. 2-In the RSA system, the one way function is multiplication and its inverse operation is factorization. The multiplication of n=p*q is simple, but to find p & q from the factorization of n is very very difficult if both p and q are large prime numbers .
Example: Let p=31, q=17. If e=7, choose d and carry out encryption and decryption for M=2. Solution: First we find n=p *q=31*17=527 ( note that this value of n will correspond to a maximum binary block of length 9 bits = INT(log2n )). ? ? = ? 1 ? 1 = 30 16 = 480 To find d, then ? ? = 1 ??? ?(?) or 7*d=1 mod 480, this is solved as k*480+1=7*d (k integer) ? =? 480+1 7 , choose smallest k such that d is an integer. The smallest k is k=5, where ? =5 480+1 C= Me mod 527= (2)7mod 527=128 Next M = Cdmod 527 = (128)343mod 527 =(35 256 35 101 47 128) mod 527=2 (128)343= ((128)2)2)2)2)2)2)2)2 1282)2)2)2)2)2 1282)2)2)2 1282)2 1282 (128) =343 7
Note: A study published later indicated that the message concealment of 2-prime RSA is not perfect, i.e. some plaintext values M are mapped into the same values i.e. C=M. To overcome this problem, this study suggested the use of 3primes or more, i.e. n=p*q*r where p, q, & r are prime numbers. Homework: carry out a numerical example for RSA with 3 primes. B]- Trap Door Knapsack public key cryptosystem: Encryption procedure: 1-Represent the message into binary form. 2-Break the binary form of the message into n-bit blocks to form the binary vector x=[x1,x2,x3, .xn] 3-Deduce the knapsack vector a"=[a1", a2", an"] with element super increasing, such that ??" > ?=1 ? 1??" ? = 1,2,..?
? 4-Select large random number m so that: ? > ?=1 5-Find random pair w and w-1such that w*w-1=1 mod m 6-Multiply each element of the ai" by w mod m to generate the public a vector: ai= w.ai" mod m 7-The ciphertext S will be: ? ??" ????where this S will be sent to the receiver. ?=1 Decryption Procedure: The receiver receives S and computes : ? = ? 1? ??? ? Then using the super increasing property of ai", the elements of the x vector will be deduced starting from the xnelement down to x1 element with a procedure similar to reducing a decimal number into binary.
To prove that this S'is the inner product < a". x >, then: ? = ? 1? ??? ? = ? 1( ????) ??? ? = ? 1( ? ??" ??? ? ??) ??? ? = [(? ? 1??? ? )??" ??? ?] ????? ? = ??" ????? ? = <a". x> Example: For n=5, say, choose the super increasing vector as: a"=(171,197,459,1191,2410) Note that each ai" is greater than the sum of previous elements. Also: ?=1 ??" = 4428 ? ???? ? = 8443 If w=170, then ? 1=? 8443+1 170 =149 5
Then ai= ai" w mod m ai=(3741,8161,2043,8281,4436) which is made public. If x=[10111] vector then: ? = ?=1 The receiver will receive S and computes S'=w-1S mod 8443 S'=149*1615 mod 8443=4231. Using S'=4231, then x5=1 since S'>a5", subtract a5" from S': 4231-2410=1821 which is greater than a4", hence x4=1. 1821-a4"=1821-1191=630>a3", hence x3=1. But (630-459)=171<a2", then x2=0. Finally, x1=1 since 171=a1". Homework: 1-Carry out another example for vector [1001101]. 2- Think about nonbinary knapsack cryptosystem. 3-Think about the one-way function of knapsack cryptosystem. 5 ??????? 8443 = 1615
Digital Signature: The public key cryptosystem can be used to solve what is called the problem of dispute. We usually used our free hand signature where everybody can recognize and we cannot deny it. Public key cryptosystem can be used to implement a digital signature of a person who cannot deny it later. Suppose that user A wishes to send a signed message M to user B, he operates on it with his secret key DAto produce the signed message S=DA(M). DAwas used as A s deciphering key when privacy was desired, but is now used as his enciphering or signing key. When user B receives S he can recover M by operating on S with the A s public key EA.
The digital signature described above does not provide protection against eavesdroppers since S can be understood by anyone. To provide privacy, user A can operate EBon S and transmit EB(S) in stead of S as a ciphertext. Only B knows DBwhere B can recover S as: S=DB(EB(S)) and again B can still save S as a proof. User B saves S as a proof that user A sent him the particular message M. If A later disclaims having sent this letter, user B can take this S to a judge who obtains EAfrom the public file and check that M=EA(S) is a meaningful message with the A s name at the end. Only user A could have generated S because only he knows DA,so A will be held responsible for having sent M. (note: this scenario is so important in banking where any customer cannot deny sending say a letter of credit to transfer funds to others).
