1
$\begingroup$

Recently I started learning how the RSA algorithm works and there is one single part of the computation which really confuses me and can't get over it.

Let's say I chose 2 prime numbers,

namely

$P = 3$ and $Q = 11$

$N = 3 \times 11 = 33$

$\phi(N) = (P-1)\times(Q-1) = 20$

Now, I have to chose e based on some criteria (as per RSA), let $e = 7$ Now, I have to determine $d$ by using, $e^{-1} \equiv1 (\bmod \phi(N))$ When I encrypt and decrypt,

a) cipher = $m ^ e \bmod N$

b) message = $c ^ d \bmod N$

In the above case, instead of $\bmod N$, for the same example, I tried different $N$ than the actual $N$ ($33$), it didn't work for any other number other than $33$. Why is it so? I can feel since finding $d$ is based on inverse under $\bmod \phi(N)$, there is some relation between $N$ and $\phi(N)$, but couldn't get my head on it.

Is there some relation between $N$ and $\phi(N)$, if so, how can I learn about it in detail?

$\endgroup$
3
$\begingroup$

RSA is based on some mathematical theorems. The first theorem that you need to learn is the Euler's Theorem; if $n$ and $a$ are coprime positive integers, then

$$a^{{\varphi (n)}}\equiv 1\bmod n.$$ when $n$ is a prime it is the Little Fermat Theorem.

This theorem tell us that in the power we use modulo $\varphi(n)$, i,e, $$a^{x} \equiv a^{x \bmod\varphi(n)} \bmod n $$

When one performs the textbook RSA encryption one calculates $$c = m^e \bmod n$$ and decryption performed as $$m = c^d \bmod n$$

Now, explicitly;

$$c^d = (m^{e})^d = m^{ed}$$ Since we choose $d$ as the inverse of $e$ modulo $\varphi(n)$, $e\cdot d = 1 \bmod \varphi(n),$ then

$$ m^{ed \bmod \varphi(n)} = m^1 = m \bmod n$$

I tried different N than the actual N (33), it didn't work for any other number other than 33. Why is it so?

Because the calculations that you performed uses modulus other than defined. $m^e$ will be a different number in a different modulus.


Note that: You used $\varphi(n) = (p-1)(q-1)$ when $n=pq$. Normally Chamichael lambda $\lambda(n)$ is used $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ and $$\varphi(n)=\lambda(n)\cdot\gcd(p-1,q-1).$$ This gives smallest $d$ to operate.

Note 2: In the above textbook RSA is used which should never be used without proper padding. For encryption, one should use RSA-OAEP which is introduced by M. Bellare, P. Rogaway. Optimal Asymmetric Encryption -- How to encrypt with RSA and PKCS#1 v1.5 padding. The former is preferable since it has security proof and PKCS#1 v1.5 PKCS1v1.5 encryption is inherently hard to use securely and should not be used.

Actually, we don't use RSA for encryption, We prefer hybrid encryption. RSA is mostly used for signatures and for signatures RSA is used with Probabilistic Signature Scheme (PSS). Again this is introduced by M. Bellare, P. Rogaway; PSS: Provably Secure Encoding Method for Digital Signatures

Remember, RSA Signing is Not RSA Decryption

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks :) it's clear $\endgroup$ – Manikandan kk Mar 9 at 11:47
  • 1
    $\begingroup$ Euler's theorem holds only when $a$ is coprime with $N$. However $a^{{\varphi (N)}+1}\equiv a\bmod N$ holds regardless, and helps make a proof that RSA works for all messages. $\endgroup$ – fgrieu Mar 9 at 18:14
  • $\begingroup$ @fgrieu yep. Let me add. $\endgroup$ – kelalaka Mar 9 at 18:15
  • $\begingroup$ "PKCS #1 v1.5 is hard to implement correctly"? memset a bunch of FFs, memcpy a constant, then memcmp? $\endgroup$ – Myria Mar 9 at 19:30
  • $\begingroup$ @Myria see the comment of Gilles. $\endgroup$ – kelalaka Mar 9 at 20:40
0
$\begingroup$

The RSA cryptosystem's parametrization depends on parameters $(p,q,e)$, where $p,q \in \mathbb{P}$ (primes) and being $e$ coprime with $N$ then $\gcd(N,e)=1$. Think this way, as $(N,e)$ is public, imagine if $\gcd(N,e)\neq 1$, then we've found either $p$ or $q$.

A simple way to proceed for RSA key generation is the following one:

  1. Select two primes numbers $p,q$ and define $N=pq$.
  2. Select $e<N$ such that $\gcd(e,N)=1$. Having a very small $e$ induces issues that could lead an attacker to key/plaintext recovery.
  3. Compute $\varphi(N)=(p-1)(q-1)$, these are the numbers coprime to $N$ less or equal than $N$. Every number that's coprime to $N$ is an unit on $Z_N^*$.
  4. Compute $\lambda(N)=lcm(p-1,q-1)$ as $Z_N^*$ is not cyclic. $Z_N^*$ has order $\varphi(N)$ but every element in $Z_N^*$ has order either $\lambda(N)$ or a divisor of this.
  5. Find $d$ such that $ed \equiv 1 \pmod{\lambda(N)}$ by Extended Euclidean.
  6. Check that it satisfies $M^{ed} \equiv_N 1$

My advice is that you can start with the so called "RSA Group" ($Z_N^*$). Toy with small primes $p,q$. Representing the multiplicative table of $Z_N^*$ helps a lot as you can notice that $\lambda(N)$ is necessary.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks :) it's clear $\endgroup$ – Manikandan kk Mar 9 at 11:47
  • 1
    $\begingroup$ $\gcd(e,N)=1$ as stated in (2) is irrelevant: it's neither necessary nor sufficient. The correct requirement is $\gcd(e,p-1)=1=\gcd(e,q-1)$. The usual way is to choose $e$ first: (2) before (1). Given how $d$ is determined in (5), the computation of $φ(N)$ serves no purpose. If a check like in (6) is made, it should be per $(M^e\bmod N)^d\bmod N=M$ for an haphazard $M\in[0,N)$, other than $0$, $1$, $N-1$, or a multiple of $p$ or $q$. E.g. $M=2$. $\endgroup$ – fgrieu Mar 9 at 18:06
  • 2
    $\begingroup$ In addition to fgrieu's correct comments, what is meant by "Having a very small $e$ induces issues that could lead an attacker to key/plaintext recovery." If it is an allusion with possible weaknesses with bad padding, well, you are well advised to use a good padding method (as a bad padding can cause additional problems not mitigated by having a large $e$) $\endgroup$ – poncho Mar 9 at 18:15

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.