Tool to decrypt/encrypt with RSA cipher. RSA is an asymetric 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: 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 idendical $ 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.

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

dCode retains ownership of the online "RSA Cipher" source code. Except explicit open source licence (indicated CC / Creative Commons / free), the "RSA Cipher" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, 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, copy-paste, or API access for "RSA Cipher" are not public, same for offline use on PC, tablet, iPhone or Android ! Remainder : dCode is free to use.

Please, check our dCode Discord community for help requests!

NB: for encrypted messages, test our automatic cipher identifier!

- RSA Decoder
- RSA Certificate Reader (N and E values)
- Complementary Helper tools
- What is 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?
- When RSA was invented?

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

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

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

Feedback

▲
Thanks to your feedback and relevant comments, dCode has developed the best 'RSA Cipher' tool, so feel free to write! Thank you!