2
$\begingroup$

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$?

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

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.

$\endgroup$
3
  • $\begingroup$ $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. $\endgroup$ May 6 '20 at 23:40
  • $\begingroup$ 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. $\endgroup$ May 6 '20 at 23:53
  • $\begingroup$ Because the modulus is small. One of the reasons for test vectors. $\endgroup$
    – kelalaka
    May 6 '20 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.