RSA Crypto System

Diffie-Hellman key exchange protocol over insecure channel gave rise to the exciting field of public key crypto system. The first practical scheme was devised by Rivest, Shamir and Adleman in 1977, based on the assumption that factorization of sufficiently large integer into their prime factors is hard. As a engineer, security practitioner, it is vital for us to understand RSA crypto system thoroughly. In this article, I explain RSA crypto primitives, correctness proof, and various known attacks. I also present benchmarking results and highlight performance of RSA crypto primitives.

In order to recall modular arithmetic you could visit https://medium.com/@prathyusha756/math-primer-to-understand-rsa-cryptographic-primitives-1e8e02760e7f

Primary application of Cryptography is to enable two parties share data confidentially.

i) Confidentiality : ensure message remain hidden from all adversaries observing the channel.
ii) Integrity: ensure message is not tampered by any adversary controlling the channel.
iii) Authentication: enable receiving entity to verify the sending entity.
iv) Non-repudiation: ensures the recipient that the sender can not later denial of the message sent.

There are two types of crypto systems: Symmetric and Asymmetric deployed in practice. In symmetric cryptography, parties first share the key and use the same key to encrypt/decrypt the messages over channel. For example, when user pay using chip card via insert/tap, chip uses the secret key to prepare cryptogram (MAC) and send to POS terminal for authorization. In this article, we focus on asymmetric cryptography and attempt explain RSA crypto system thoroughly.

1.1 Asymmetric cryptography
Asymmetric cryptography is also known as public key cryptography(Shown in Figure .1). Two parties(e.g. Alice and Bob) generate key pair(secret and public key) individually, and share public keys with each other. Alice uses Bob’s public key to encrypt the message and Bob decrypt the message using his secret key.

In the case of symmetric key cryptography Alice and Bob share a secret key via secure channel. The secret key can be used to encrypt as well as to decrypt the message from cipher text. In general, symmetric key cryptography is significantly faster than asymmetric cryptography.

1.1.1 Advantages of Asymmetric cryptography
1. In asymmetric key cryptography there is no need to share secret keys among parties a priori, thus eliminates the key distribution problem.
2. In asymmetric key cryptography each user has to maintain a key pair(public key, private key). public keys are accessible to the public, so anyone can send a message to the recipient by using recipient’s public key. Where as in symmetric key cryptography for ’n’ number of users, each user has to manage (n-1) number of keys. In asymmetric key cryptography, one has to manage just one private key securely.

1.2 Security Assumptions
Security of the Public key crypto system can be realized using various computationally hard problems — — factorization (RSA), DLP (Discrete Logarithm Problem). In this article our main concern is RSA asymmetric algorithm.

2. Security definitions
2.1 Cipher text only attack(COA) or known cipher text attack :
In cipher text only attack, attacker has access to the set of cipher texts. If the attacker is able to get the plain text or the key that is used to decrypt the message with the available cipher-text then the attack is known as cipher text only attack. Every modern cipher tries to provide protection against cipher text only attack because the attack can be easily carried out. The attacker just need to eavesdrop on the channel to get the cipher text.

2.2 Known plain text attack :
Attacker has access to some of the plain texts and it’ s corresponding cipher-texts. With this information, if the attacker is able to decode some other cipher text which is generated using the same key, then the attack is called as known plain-text attack. In order to carry out this attack, attacker just needs to eaves drop on the public communication channel to get cipher texts. Corresponding plain texts often can be guessed in some cases. For example, every conversation starts with hi or hello.
All classical ciphers are susceptible to known plain text attack. For example shift cipher(Ceaser cipher), If you are able to decode one letter from the cipher text then you could simply decrypt entire cipher text.

2.3 Chosen plain text attack :
Attacker some how influence the sender to encrypt the plain text of his choice. The corresponding cipher-text can be observed by the attacker when it was sent over the communication channel. With this information attacker tries to get the information about private key and about the system.

2.4 Chosen cipher text attack :
Chosen cipher text attack is even more powerful than the chosen plain text attack. In chosen cipher text attack, attacker able to get the decryption of cipher texts of his choice in addition to the encryptions of the plain texts of his own choice. Adversary have an access to these encryption and decryption blocks without any time limit. But attacker can not request these decryption oracle to get the plain text of the challenged cipher text.
Chosen cipher text security(CCA-secure) possesses a property non-malleability. A non-malleable system is that, if the attacker modifies a given cipher text(it does not look at all like challenged cipher text) and send it to the decryption oracle. The decryption oracle either produces a message invalid cipher text or the decryption of cipher text(plain text). But the produced plain text should not have no relation to the original plaint text.

3. RSA Assumptions :
Security of RSA depends on the difficulty in factoring large integers.

For Example: p=885320963, q=238855417 then
n = p*q = 211463707796206571.
Given ’n’, there is no known polynomial time algorithm exists to find p and q.
If you have given n then coming with two unique prime numbers where it’s product is equal to n, is very difficult. As ’n’ value increases the difficulty of factoring that number goes to exponential increase.
On intel core machine, i5 (@ 1.8 GHz), it takes 34 ms to factorize 20 bit number. where as to factor 1024 bit number it takes
(2¹⁰²⁴ / 2²⁰) * 34 ms = 5.83 * 10³⁰⁰ years approximately.

3.1 Text book RSA

3.1.1 Key generation :
1. Choose two large prime numbers p, q.
2. Calculate n, ɸ(n). where n=p*q. ɸ(n)=(p-1)(q-1) here ɸ(n) is Euler’s totient function.
3. Choose ‘e’(encryption exponent) randomly such that 1< e < ɸ(n) and gcd(e, ɸ(n))=1.
4. Calculate ‘d’(decryption exponent) such that e*d = 1 (mod ɸ(n)).
5. Public key pk= (n, e).
6. Private key sk=(n, d).

3.1.2 Encryption :
Let say Alice wants to send message ‘m’ to Bob. Alice uses Bob’s public key(pk) to encrypt message ‘m’.

Cipher text(c) = mᵉ (mod n).

3.1.3 Decryption :
After Bob received a message from Alice, Bob uses his private key( sk) to decrypt message.

message(m) = cᵈ (mod n).

3.1.4 Correctness of RSA
Let’s take cipher text ‘c’. In order to recover message ‘m’, Bob computes
1. cᵈ = (mᵉ)ᵈ = mᵉᵈ (mod n).
we know, e*d =1 (mod ɸ(n))=1+k ɸ(n). where k is some integer.

2. where cᵈ = mᵉᵈ (mod n) = m^{1+k ɸ(n)} (mod n) = m(m^{kɸ(n)}) (mod n).

We know that, If x=a (mod p) and x=a (mod q), then x= a (mod p*q) where p, q are distinct prime numbers.

3. So if we could prove that cᵈ = mᵉᵈ (mod p)= m (mod p) and cᵈ= mᵉᵈ (mod q) = m (mod q) then automatically cᵈ = mᵉᵈ (mod n)= m (mod n).

4. Let’s take cᵈ=mᵉᵈ (mod p)

case i : From Euler’s theorem, if gcd(a, n)=1 then a^{ɸ(n)} (mod n)=1 (mod n).

So, if gcd(m, p) =1 then m^{ɸ(p)} (mod p) = 1 (mod p).

cᵈ= m( m^{kɸ (n)})(mod p)=m(m^{k*ɸ(p)* ɸ(q)})(mod p) = m*(1)^{k*ɸ(q)} (mod p) = m.

case ii : If gcd (m, p)=p then m= 0(mod p).

Therefore cᵈ = m(m^{kɸ(n)}) (mod p)=0 (mod p)=m.

Therefore cᵈ = m^{ed} (mod p)=m (mod p).

Similarly cᵈ = m^{ed} (mod q)= m (mod q)

Finally we could conclude that cᵈ= mᵉᵈ (mod p*q)= m (mod n).

3.2 Digital signature
Digital signature is used to sign electronic documents . It provides authenticity(i.e from whom we have received a message), integrity(message is not changed in the transit).
Let say Alice wants to send message(m) to Bob. Alice uses Bob’s public key( pk) to encrypt the message. Bob receives the cipher text(c), but at this point Bob might not know that who sent the message. Because Bob’s public key pk is publicly available, any one can send a message. Digital signature help Bob to authenticate Alice, before processing the encrypted message.

3.2.1 Plain RSA signature scheme
Let’s discuss plain RSA signature scheme. It involves three steps.

i) Key generation : Generate public key pk=(n, e), private key sk = (n, d).
ii) Signature generation: Let’s take the message(m), private key sk and compute signature.
𝝈 = mᵈ (mod n).
iii) Signature verification: By using public key pk, compute 𝝈ᵉ (mod n), see whether it is equal to message m or not. If it is equal then we can say that this is valid signature.

But this signature scheme is vulnerable to no-message attack and attacker is able to forge a signature on an arbitrary message.

1.No-message attack: In this attack, attacker forge a signature just with a knowledge of public key. First attacker calculate uniform 𝝈 then calculates message using public key pk=(n, e) as m=𝝈ᵉ (mod n). Attacker sends (m, 𝝈) to the recipient. Here 𝝈 is a valid signature but it was not issued by an actual sender. In this attack, attacker chooses 𝝈 in such a way that to influence the resulting message.

2. Forging a signature on an arbitrary message : This one is even more powerful than the previous attack. Here attacker requests signatures on ’n’ number of random messages M={m1, .., mn} from the sender. With this information attacker could generate signatures on 2ⁿ-n number of other messages which are generated from product of subsets of M.

𝝈 = H(m)ᵈ (mod n).

After Bob receives a cipher text(c), decrypt the cipher text(c) by using Bob’s private key. He gets message(m), digital signature(𝝈).

ii) Verify a digital signature:

Step 1:Take the message(m) and passed to the hash function. Finally it generates some hash code(H(m)).

Step 2:Take the Digital signature(𝝈) and decrypt it using Alice’s public key . Finally we get some hash code.

If the hash code generated by the Step 1 and Step 2 are equal then we can say that signature is valid.
𝝈ᵉ = H(m)(mod n).

3.3 Attacks against Text Book RSA:
3.3.1 Malleability Attack :
Text book RSA is malleable. A crypto algorithm is said to be malleable, if the attacker is able to change a cipher text(c) in such a way that it could produce related plain text. Attacker doesn’t have any knowledge about plaintext. Let say cipher text(c)=mᵉ. Attacker changed it as c’=(2ᵉ)*c=(2*m)ᵉ. Finally receiver decrypts c’ and gets plaintext 2m.
Malleability is not a desired property, for example if the message (m) is a bank transaction, attacker could simply change the amount. So this attack rises serious concerns particularly in the case of sensitive applications.

3.3.2 Chosen cipher text Attack :
Let say attacker have the information about cipher text(c)=mᵉ. Attacker wants to change the cipher text(c) as c’=mᵉ*rᵉ, where ‘r’ is some random number. Attacker may ask the person who have private key(d) to decrypt the unmalicious-looking cipher text(c’). Attacker gets c’ᵈ=m*r. Dividing above equation by ‘r’, attacker finally able to get message ‘m’.

3.3.3 Timing Attack :
This is one of the side channel attacks. Side channel attacks can be performed only if you know the details of the computer system in which the cryptographic algorithm is running. With this information attacker able to find the time needed to decrypt the several cipher texts and finally able to find out the secret key.

In order to protect from this attack, we can make sure that every decryption of the cipher text takes constant time. But it effects the system performance. Rather than the mentioned approach, RSA implementation uses ‘Cryptographic blinding’ technique. It works as follows, Instead of decrypting cipher text(c), first multiply with rᵉ where ‘r’ is a random number, ’e’ is encryption constant. We get c’=c*rᵉ, After decrypting c’ᵈ=m*r. Multiply c’ᵈ with r⁻¹ we get message(m).

3.4 Practical RSA

3.4.1 RSA PKCS#1 v1.5 Padding Scheme
A crypto system is said to be semantically secure, if it could produce different cipher texts for the same plaintext. Let say plaintext(m) is encrypted and produced cipher text(c), If you encrypt ‘m’ again then it should produce some other cipher text(c’). So attacker doesn’t get a chance to learn about plain text. Our Text book RSA is not semantically secure because encrypting the same plain text produces same cipher text.

In order to solve this problem, standards such as PKCS was developed to pad the message(m) with random number of bits before going to the RSA encryption.

We know RSA public key is pk=(e, n), where ‘e’ is the encryption exponent, n is a large prime number. let k denotes length of ’n’ in bytes. Let’s take message ‘m’ to be encrypted of its length(l) in multiples of bytes and in the range of one to k-11 bytes. ‘r’ is randomly generated byte string of it’ s length is equal to the k-l-3 and none of its bytes should not be 0x00.

â= [(0x00 || 0x02 || r||0x00||m)]

The resulting message â is constructed with, initial two blocks of length 2-bytes(0x00 ||0x02) then concatenated with randomly generated byte string ‘r’ and one byte of zero’s followed by message ‘m’.

Cipher text c = (â)ᵉ (mod n).

If the random padding is too short then PKCS#1 v 1.5 is not CPA-secure and liable to many attacks. So length of random padding ‘r’ should be at least

‖n‖ /e.

Decryption of cipher text: cᵈ(mod n)=â. message ‘m’ can be recovered as the least significant bits(k-length of ‘r’ -2) of â. When the receiver decrypts the cipher text, First receiver checks the most two significant bytes values and their values should be equal to the 0x00 ‖ 0x02. If not, receiver send a error message ‘invalid cipher text’. Let see how this error message leads to serious consequences.

let say attacker eavesdrop on the public communication channel and got a cipher text ‘c’ which he wants to decrypt it. Attacker pick a random number r’ and calculates c’=r’c. The resulting cipher text c’ is sent to the receiver. The receiver checks whether c’ in proper format or not. If not, receiver send a error message.
Based on the receiver response attacker come to know that the decryption of c’ can generate most two significant bytes values equal to the 0x00 ‖ 0x02 or not. Attacker also have his decryption oracle which checks the decryption of c’’s most two significant bytes are equal to 0x00 ‖ 0x02 or not. Bleichenbacher proves that the attacker is able to decrypt ‘c’ using this decryption oracle.

In order to protect from these type of attacks a new standard optimal asymmetric encryption padding(OAEP) was developed.

For encryption constant e=65537=2¹⁶+1 , encryption operation require total 17 multiplications which are far less than the multiplications required for randomly selected ‘e’. By using the mentioned value for ‘e’ we could increase the efficiency of encryption scheme.

3.6 Benchmarking
I implemented the RSA crypto system using JAVA on Intel machine (i5, @1.8GHz). The following figure highlights the performance of encryption, decryption, signature generation and verification. Results show that RSA performs poorly as the key size increases from 512 bits to 4096 bits. In the below figure X- axis indicates key length, Y-axis indicates number of operations(encryptions/decryptions/signature generations and verifications) per second.

3.7 Conclusion
RSA crypto system is deployed widely and it is strongly recommended for software engineers, practitioners and security enthusiasts to understand the system thoroughly. In this article, we explained text book RSA primitives, security definitions, various attacks and practical implementation of the RSA.

References:

Related posts:

It has been ages that we have been using shared preference to store data in local storage in a key pair format or using SQLite for storing data in SQL database. The other way to store local data is…

With each passing year, the concept of data as the new ‘oil’ has been receiving greater and greater acceptance, and understandably so, since data utilization is driving greater precision in decision…

Notes on Suicide for the Passing of Anthony Bourdain. People end their lives to avoid a fate worse than death. Sometimes it concerns a temporary problem, but more often than not they had a….