# Problem with RSA deciphering

I don't quite get the algorithm yet. Sometimes it works and other times it doesn't,so clearly I am overseeing or misunderstanding something.

I will just write what I did. My $$N=143$$ and has factors $$p=11$$, and $$q=13$$. To determine my second public number: $$R=(p-1)(q-1)= 10 \cdot12=120$$. So the second number can not be a factor of $$120$$. I figured $$e=7$$ would be fine.

I simply want to message $$'7'$$. So $$\mod\frac{7^7}{143}= 6$$ will be my message.

My friend wants to decode it and needs to exponentiate this number by $$d$$. $$d=\frac{R+1}{e}=121/7$$ But this should be natural number right?

I noticed it doesn't work for $$e=9$$ as well. Even though it is not a factor of $$120$$. It does work for $$e=11$$.

Should $$e$$ be chosen so that it is a factor of $$R+1$$?

• $c = m^e \bmod n$ so $c = 7^7 \bmod 143$. Did you read the RSA on Wikipedia? – kelalaka May 6 '20 at 22:34
• No, on some other article. But $c=6$ only the deciphering goes wrong. – Jordy Molenaar May 6 '20 at 22:39
• I am reading on Wikipedia now and I am indeed missing a lot of crucial steps in the algorithm. – Jordy Molenaar May 6 '20 at 22:42
• So $\lcm{10,12}=60$ and $\gcd{7,60}=1$ So $e=7$ should be a valid candidate. – Jordy Molenaar May 6 '20 at 22:51

For textbook RSA, we have

Key-Gen

• The modulus $$n$$ must be a product of two distinct random large primes due to the security, $$n = p \cdot q$$

in your case $$n=143 = 11\cdot 13$$

For finding the primes, the probabilistic Miller–Rabin primality test, it should be enough. Note that the Miller–Rabin primality test is probabilistic; composite output is always true, prime output has probability defined by the number iterations, $$k$$; $$\Pr( p\text{ is not prime} ) \ll \frac{1}{4^k}$$ and can be stated as $$\log_2(\Pr( p\text{ is not prime} ))\ll-2k$$ This is a rough calculation, and as noted by fgrieu, the probability is approaching 0 as the size of the number to be tested increases. The FIPS 186-4 table C.3 provides specific numbers for $$k$$;

• for 512 bits gives $$k=7$$ rounds with $$\log_2(\Pr( p\text{ is not prime} ))<-100$$,
• for 1024 bits gives $$k=4$$ rounds with $$\log_2(\Pr( p\text{ is not prime} ))<-100$$, and
• for 1536 bits gives $$k=3$$ rounds with $$\log_2(\Pr( p\text{ is not prime} ))<-100$$.
• The factors of modulus are $$p=11$$ and $$q =13$$

• $$\varphi(n) = (p-1)(q-1)$$, in your case $$\varphi(143) = 10\cdot 12 = 120$$,

Actually, we prefer $$\lambda(n) = \operatorname{lcm}(p,q)$$ and this will give us the smallest private exponent. That can be helpful for signature calculation speed, and actually, one should use the CRT method ( see the last bullet of Key-Gen)

The relation is; $$\varphi(n)=\lambda(n)\cdot\gcd(p-1,q-1)$$ and this implies that $$\lambda(n)| \varphi(n)$$

• The public exponent $$e$$ is chosen relatively prime to $$\varphi(n)$$, so $$e=7$$ is fine. Normally the $$e$$ is chosen advance in $$\{3, 5, 17, 257, 65537\}$$. If the $$\gcd(e,\varphi(n)) \neq 1$$ then a new modulus is generated.

$$(n,e)$$ makes the public key to distribute.

• The private exponent $$d$$ is the inverse of $$e$$ modulo $$\varphi(n)$$, i.e. $$d\cdot e \equiv 1 \bmod \varphi(n)$$, in your case $$d=103$$. This can be used with the Ext-GCD which result in a Bézout's identity $$e \cdot x + n \cdot k =1$$. Take modulus $$n$$ then $$x$$ is the inverse of $$e$$.

$$(n,e,d,p,q, d_p, d_q, q_{inv})$$ is your private key. One can use CRT to speed up the decryption up to 4 times.

Encrypt

• $$c = m^e \bmod n$$

The $$m \in [0,n)$$, otherwise after the decryption one will get an equivalence class representative of $$m$$ less then $$n$$.

Decrypt

• $$m = c^d \bmod n = (m^{e})^{d} \bmod n = m^{ed} \bmod n = m$$

Example

• $$m = 7$$ then $$c = 7^7 \pmod{143} = 6$$

• $$m = 6^{103} \pmod {143}= 7$$

Notes:

1. There is also multi-prime RSA where the large prime factors of $$n$$ are mode than 2.
2. Textbook RSA is not secure one should never use it without a proper padding scheme. One is the PKCS#v1.5 padding scheme and the other is RSA-OAEP. RSA OAEP has a security proof and PKCS#v1.5 has not. PKCS#v1.5 has many attacks over the years and should not be used.

3. RSA ( actually any public-key encryption) is not preferable due to the speed. We prefer the hybrid encryption schemes like RSA-KEM for Key Encapsulation Mechanism then encrypt the data with AES-GCM or ChaCha20-Poly-1305 to achieve Data Encapsulation Mechanism, use 256 bit key with AES, preferably.

With this composition of a KEM and a DEM, one can achieve IND-CCA2/NM-CCA2—ciphertext indistinguishability and nonmalleability under adaptive chosen-ciphertext attack.

• $d\cdot e = 1 \mod{\phi(n)}$ is to be solved. I understand $103\cdot 7 = 721$ and this works because $6\cdot 120= 720$. Only I am nowhere near familiar with modulo and the algorithms. I see one can use extended euclidean algorithm. – Jordy Molenaar May 6 '20 at 23:40
• But I will certainly look into it. I realise I miss vital operation and understanding. It's funny because it actually worked quite a few times with the wrong approach. abc.net.au/news/science/2018-01-20/… (at the end it tells how to calculate e and d. – Jordy Molenaar May 6 '20 at 23:53
• Because the modulus is small. One of the reasons for test vectors. – kelalaka May 6 '20 at 23:54