Score:0

Crypto

RSA: why $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{mod}~ \varphi(n)$ holds for a specific setting of RSA

Cryptomathician

2/23/23, 2:51 PM

Let $p,q$ are primes and $n = pq$ as in every RSA setting and now use a random $e$ that holds the following properties

$gcd(e, \phi(n)) \neq 1$
$(e^{-1} ~\text{mod} ~\phi(n))^{4}\cdot3 < n$
$e^{-1} ~\text{mod} ~\phi(n) < \sqrt[3]{n}$ (integer square root), where $\sqrt[3]{n} \in \mathbb{Z}$

where $\phi$ is euler's totient function. This $e$ is used as the public exponent for the public key and $d$ is the private exponent for the private key.

Remember that $\phi(n) | ed - 1$, as $ed = 1 + k \cdot \phi(n)$ holds for $k \in \mathbb{Z}$. The question is, why it holds that $$(e^{-1} ~\text{mod}~ n \cdot \phi(n)) ~\text{mod}~ \ \phi(n) = e^{-1} ~\text{mod}~ \phi(n)\text{?}$$ Could someone explain it mathematically or give a proof why that holds?

A related question regarding multiple of $\phi(n)$ is asked in this question. Unfortunately, I don't understand the relation between the multiple of $\phi(n)$, the $gcd$ and why this equation $ed = 1 ~\text{mod}~ k \cdot \phi(n)$ holds $ed = 1 ~\text{mod}~ \phi(n)$ for $k \in \mathbb{Z}$.

Additionally it would be nice to read a proof for the related question regarding the multiple of $\phi(n)$, if someone knows why that holds.

0 + 0

rsa

number-theory

poncho

2/23/23, 7:22 PM

$(e^{-1} \bmod \phi(n))^4 \cdot 3 < n$ is certainly not standard with RSA, and I probably yields an RSA public key that is vulnerable to attack. Are you modelling such a weak RSA key?

Cryptomathician

2/23/23, 7:49 PM

Yes, it should be vulnerable. @poncho

Score:1

Crypto

poncho

2/23/23, 7:14 PM

The question is, why it holds that $(e^{−1} \bmod n \cdot \phi(n)) \bmod \phi(n)=e%{−1} \bmod \phi(n)$?

Actually, we have the more general identity $(A \bmod BC) \bmod C \equiv A \bmod C$, for any integers $A, B, C$. In your specific case, we have $A = e^{-1} \bmod \phi(n)$, $B = n$, and $C = \phi(n)$

This more general identity can be easily be seen from two facts:

$X \bmod Y = X + k \cdot Y$ for some integer $k$ (which may be negative)

$X \bmod Y = Z \bmod Y$ if and only if $X - Z = k'\cdot Y$ for some integer $k'$.

From the first fact, we can see that $A \bmod BC = A + kBC$ (for some integer $k$ - we don't care what that integer is)

From the second fact, we see that $(A + kBC) \bmod C = A \bmod C$ holds if we have $A + kBC - A = k'C$ for some integer $k'$; we can immediately see that this holds for the integer $k' = kB$, hence this is true.

Since the general identity holds in all cases, it also holds in your specific case.

0 + 0

Cryptomathician

2/23/23, 7:56 PM

thank you. I am wondering where the gcd plays a role like it is mentioned in the "correct" answer of the related question on the mathoverflow stackexchange. Should be e and n coprime ($gcd(e,n)$) to hold that identity?

poncho

2/23/23, 10:32 PM

@Cryptomathician: well, if $e$ and $n$ are not relatively prime, then $e^{-1} \bmod (n \cdot \phi(n))$ wouldn't exist.

Cryptomathician

2/23/23, 10:46 PM

ok, got it. Thank you for the detailed explanation.

Cryptomathician

2/23/23, 11:33 PM

is it a different question when I want to know when $y = x^{-1} ~(\text{mod}~ k \cdot \phi(n))$ holds, so that also $xy \equiv 1 ~(\text{mod}~ \phi(n))$ holds for some $k \in \mathbb{Z}$ ? I was trying to figuring out when this holds, too. @poncho

poncho

2/24/23, 2:42 AM

@Cryptomathician: actually, it holds for all $k \in \mathbb{Z}$; same sort of logic: $y = x^{-1} \pmod{k \phi(n)}$ means there is a $k' \in \mathbb{Z}$ with $yx = 1 + k'( k \phi(n))$; this implies that there is a $k''$ with $yx = 1 + k'' \phi(n)$, that is, $yz \equiv 1 \pmod{\phi(n)}$

Cryptomathician

2/24/23, 2:48 AM

Ok, thank you. I did the same calculation as you did and wanted to be sure that I don't made a mistake. Thank you! Probably the last equation should be $yx \equiv 1 ~(\text{mod}~ \phi(n))$ instead of $yz \equiv 1 ~(\text{mod}~ \phi(n))$ right?

poncho

2/24/23, 11:43 AM

@Cryptomathician: correct, $yz$ was a typo...

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: RSA: why $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{mod}~ \varphi(n)$ holds for a specific setting of RSA

TH: RSA: ทำไม $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{ mod}~ \varphi(n)$ ไว้สำหรับการตั้งค่าเฉพาะของ RSA

RO: RSA: de ce $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{ mod}~ \varphi(n)$ este valabil pentru o anumită setare a RSA

RU: RSA: почему $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{ mod}~ \varphi(n)$ выполняется для конкретной настройки RSA

VI: RSA: tại sao $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{ mod}~ \varphi(n)$ giữ cho một cài đặt cụ thể của RSA

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.