Linked Questions

20 votes
4 answers

Why do we need Euler's totient function $\varphi(N)$ in RSA?

After we calculated $N = p * q$, we calculate $\varphi(N)$ and use it later to determine $e$ (PR) and $d$ (PU). But why? For decryption and encryption, we only use $N$ and don't need $\varphi(N)$. So ...
Rimen's user avatar
  • 219
15 votes
2 answers

RSA Proof of Correctness

Can anyone provide an extended (and well explained) proof of correctness of the RSA Algorithm? And why is it needed? I can't say that this or this helped me much, I'd like a more detailed and newbie ...
Matteo's user avatar
  • 1,131
4 votes
1 answer

Is encryption time greater than decryption time?

Is encryption time always greater than decryption time for all encryption techniques (AES / DES / RSA / DSA), or is there a mistake somewhere in my implementation?
user avatar
2 votes
1 answer

How can I use eulers totient and the chinese remainder theorem for modular exponentiation?

I'm trying to implement modular exponentiation in Java using Lagrange and the Chinese remainder theorem. The example we've been given is: Let $N = 55 = 5 · 11$ and suppose we want to compute $27^{...
Saf's user avatar
  • 205
3 votes
1 answer

Space needed to store an RSA private key

How much space is actually needed to store a $4096$-bit RSA private key? I originally assumed $0.512$ kB since $\frac{4096}{8} = 512$, but then I started to wonder whether it was in hex. Simply, what'...
Awn's user avatar
  • 1,532
3 votes
1 answer

What is the private key in RSA?

I'm new to cryptography and I have a doubt: I read some pages a bit different definition for the RSA private key: In 1 - (n, d) In 2 - ...
eightShirt's user avatar
1 vote
1 answer

DGK Cryptosystem Encryption Speedup

Following @poncho's nice clarification of the RSA speedup here, let's see if I'm able to do the same in the case of the DGK cryptosystem: We have pk = (n, g, h, u), sk = (p, q, $v_p$, $v_q$) which ...
Mihai Todor's user avatar
2 votes
1 answer

Pick faster private exponent

I recently tried to send 1536-bit modulus CSR to COMODO. They refused to sign the certificate. I later found out that it's because NIST mandated 2048-bit modulus on the SSL certificate. I think it's ...
Curious Sam's user avatar
0 votes
1 answer

What information is needed to be stored for RSA private key for decryption

I am using rsa module in Python. I use the following line to generate public and private key: ...
user9278661's user avatar
2 votes
1 answer

Montgomery Multiplication with CRT

I am attempting to understand how to use Montgomery multiplication in an RSA private key operation: $X \equiv a^{e} \pmod{n}$ where $a$ is the message, $e$ is the exponent, $n$ is the modulus. Using ...
Henry Bergin's user avatar
1 vote
1 answer

Faster alternatives to RSA trapdoor permutation

We're working on web3.0 decentralized internet, a big part of which is a decentralized file storage system where clients upload files to storage providers and pay them for the services. Storage ...
Serge Uvarov's user avatar
1 vote
1 answer

Creating hash data signatures using RSA-CRT

I have taken two prime numbers p=137 q=131 M=64 and i want to create a digital signature ...
Sai Teja T's user avatar
1 vote
1 answer

Could someone please elaborate on how $(c^d \bmod n) \bmod p = c^d \bmod p$, given that $n = pq$, where $p$ and $q$ are prime numbers?

I'm following this (Chinese Remainder Theorem and RSA) post, but I don't understand how $(c^d \bmod n) \bmod p = c^d \bmod p$. Being told that it's because $n=pq$ is not enough for me to understand. ...
Alfred Kaminski's user avatar