Tool to decrypt/encrypt with RSA cipher. RSA is an asymmetric algorithm for public key cryptography created by Ron Rivest, Adi Shamir and Len Adleman. It is the most used in data exchange over the Internet.

RSA Cipher - dCode

Tag(s) : Modern Cryptography, Arithmetics

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!

A suggestion ? a feedback ? a bug ? an idea ? *Write to dCode*!

⮞ Go to: Prime Factors Decomposition

⮞ Go to: Multiplication

⮞ Go to: Multiplication

⮞ Go to: Modular Multiplicative Inverse

⮞ Go to: Prime Numbers Search

⮞ Go to: Modular Exponentiation

⮞ Go to: Hexadecimal (Base 16)

⮞ Go to: Base64 Coding

⮞ Go to: File Creation

RSA encryption (named after the initials of its creators Rivest, Shamir, and Adleman) is the most widely used asymmetric cryptography algorithm. Based on mathematical and arithmetic principles of prime numbers, it uses large numbers, a public key and a private key, to secure data exchanges on the Internet.

RSA encryption is purely mathematical, any message must first be encoded by integers (any encoding works: ASCII, Unicode, or even A1Z26). For RSA encryption, the numbers $ n $ and $ e $ are called public keys.

The (numeric) message is decomposed into numbers (less than $ n $), for each number `M` the encrypted (numeric) message `C` is $$ C \equiv M^{e}{\pmod {n}} $$

__Example:__ Encrypt the message `R,S,A` (encoded `82,83,65` in ASCII) with the public key $ n = 1022117 $ and $ e = 101 $ that is $ C = 828365^{101} \mod 1022117 = 436837 $, so the encrypted message is `436837`.

Decryption requires knowing the private key $ d $ and the public key $ n $. For any (numeric) encrypted message `C`, the plain (numeric) message `M` is computed modulo `n`: $$ M \equiv C^{d}{\pmod {n}} $$

__Example:__ Decrypt the message `C=436837` with the public key $ n = 1022117 $ and the private key $ d = 767597 $, that is $ M = 436837^{767597} \mod 1022117 = 828365 $, `82,83,65` is the plain message (ie. the letters `R,S,A`)

RSA needs a public key (consisting of 2 numbers $ (n, e) $) and a private key (only 1 number $ d $).

— Select 2 distinct prime numbers $ p $ and $ q $ (the larger they are and the stronger the encryption will be)

— Calculate $ n = p \times q $

— Calculate the indicator of Euler $ \phi(n) = (p-1)(q-1) $

— Select an integer $ e \in \mathbb{N} $, prime with $ \phi(n) $ such that $ e < \phi(n) $

— Calculate the modular inverse $ d \in \mathbb{N} $, ie. $ d \equiv e^{-1} \mod \phi(n) $ (via the extended Euclidean algorithm)

With these numbers, the pair $ (n, e) $ is called the public key and the number $ d $ is the private key.

__Example:__ $ p = 1009 $ and $ q = 1013 $ so $ n = pq = 1022117 $ and $ \phi(n) = 1020096 $. The numbers $ e = 101 $ and $ \phi(n) $ are prime between them and $ d = 767597 $.

The keys are renewed regularly to avoid any risk of disclosure of the private key. It is essential never to use the same value of p or q several times to avoid attacks by searching for GCD.

Using identical $ p $ and $ q $ is a very bad idea, because the factorization becomes trivial $ n = p^2 $, but in this particular case, note that $ phi $ is calculated $ phi = p(p-1) $

The message is fully digital and is normally accompanied by at least one key (also digital).

In practice, the keys are sometimes displayed in hexadecimal, or stored in a certificate (encoded in base64).

The length of depends on the complexity of the RSA implemented (1024 or 2048 are common)

RSA encryption is used in the HTTPS protocol

**Method 1: Prime numbers factorization** of $ n $ to find $ p $ and $ q $.

The RSA cipher is based on the assumption that it is not possible to *quickly* find the values $ p $ and $ q $, which is why the value $ n $ is public. To find the private key, a hacker must be able to perform the prime factorization of the number $ n $ to find its 2 factors $ p $ and $ q $. In practice, this decomposition is only possible for *small* values, i.e. a key $ n $ comprising less than 30 digits (for current algorithms and computers), between 30 and 100 digits, counting several minutes or hours, and beyond, calculation can take several years. With $ p $ and $ q $ the private key $ d $ can be calculated and the messages can be deciphered.

**Method 2: Find the common factor** to several public keys $ n $

Key generation is random but it is not unlikely that a factor $ p $ (or $ q $) could be used to calculate the values of 2 different public keys $ n $. By calculating the GCD of 2 keys, if the value found is different from 1, then the GCD is a first factor of $ n $ (therefore $ p $ or $ q $), by dividing $ n $ by the gcd is the second factor ($ p $ or $ q $).

**Method 3: Chosen ciphertext attack**

Given a published key ($ n $, $ e $) and a known encrypted message $ c \equiv m^e \pmod{n} $, it is possible to ask the correspondent to decrypt a chosen encrypted message $ c' $. Based on the property $ m_1^e m_2^e \equiv (m_1 m_2)^e \pmod{n} $, the decryption of a message $ c' \equiv c \times r^e \pmod{n} $ with $ r $ a chosen number (invertible modulo $ n $) will return the value $ m \times r \pmod{n} $. By calculating $ m \times r \times r^{-1} \pmod{n} $ (with $ r^{-1} $ the modular inverse) is found $ m $ the original message.

**Method 4: Problem with short messages with small exponent $ e $**

For a small exponent ($ e = 3 $) and a short message $ m $ (less than $ n^{1/e} $) then the encrypted message $ c = m^e $ is less than $ n $, so the calculation of the modulo has no effect and it is possible to find the message $ m $ by calculating $ c^(1/e) $ ($ e $-th root).

**Method 5: Wiener's attack for private keys $ d $ too small**

If the private key $ d $ is small compared to the message $ n $ and such that $ d < \frac{1}{3} n^{\frac{1}{4}} $ and that $ p $ and $ q $ are close $ q < p < 2q $, then by calculating approximations of $ n/e $ using continued fractions, it is possible to find the value of $ p $ and $ q $ and therefore the value of $ d $.

To find the private key, a hacker must be able to realize the prime factor decomposition of the number $ n $ to find its 2 factors $ p $ and $ q $. For small values (up to a million or a billion), it's quite fast with current algorithms and computers, but beyond that, when the numbers $ p $ and $ q $ have several hundred digits, the decomposition requires on average several hundreds or thousands of years of calculation. There are databases listing factorizations like here (link)

With the numbers $ p $ and $ q $ the private key $ d $ can be computed and the messages can be decrypted.

The value $ e=65537 $ comes from a cost-effectiveness compromise.

A value of $ e $ that is too large increases the calculation times. A value of $ e $ that is too small increases the possibilities of attack.

$ 65357 $ is a Fermat number $ 65357 = 2^{2^4} + 1 $ which allows a simplification in the generation of prime numbers.

This value has become a standard, it is not recommended to change it in the context of secure exchanges.

The number found is an integer representing the decimal value of the plaintext content.

Generally, this number can be transcribed according to the character encoding used (such as ASCII or Unicode).

__Example:__ The whole number `431164974181` has hexadecimal writing `64,63,6F,64,65` i.e. the characters `D,C,O,D,E` (in ASCII code)

An RSA certificate is a text file containing the data useful for a cryptographic exchange by RSA.

There are 2 types of certificate:

— the public certificate, which begins with `-----BEGIN PUBLIC KEY-----` and which contains the values of the public keys $ N $ and $ e $.

— the private certificate, which starts with `-----BEGIN RSA PRIVATE KEY-----` and which contains all the values: $ N $, $ e $, $ d $, $ q $ and $ p $. This file is usually kept safe and should never be disclosed.

Ronald Rivest, Adi Shamir and Leonard Adleman described the algorithm in 1977 and then patented it in 1983.

dCode retains ownership of the "RSA Cipher" source code. Except explicit open source licence (indicated Creative Commons / free), the "RSA Cipher" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "RSA Cipher" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "RSA Cipher" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!

Reminder : dCode is free to use.

The copy-paste of the page "RSA Cipher" or any of its results, is allowed (even for commercial purposes) as long as you cite dCode!

Exporting results as a .csv or .txt file is free by clicking on the *export* icon

Cite as source (bibliography):

*RSA Cipher* on dCode.fr [online website], retrieved on 2023-05-31,

- RSA Decoder
- RSA Certificate Reader
- Complementary Helper tools
- What is the RSA cipher? (Definition)
- How to encrypt using RSA cipher?
- How to decrypt a RSA cipher?
- How to generate RSA keys?
- How to recognize RSA ciphertext?
- What are possible RSA attacks?
- How to decrypt RSA without the private key?
- Why using the number e=65537 for RSA?
- How to decrypt a number into plaintext?
- What is an RSA certificate?
- When was RSA invented?

rsa,https,key,public,private,rivest,shamir,adleman,prime,modulo,asymmetric

https://www.dcode.fr/rsa-cipher

© 2023 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback