Linked Questions

16
votes
4answers
11k views

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 ...
14
votes
3answers
28k views

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 ...
4
votes
1answer
7k views

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?
2
votes
1answer
5k views

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^{...
3
votes
1answer
2k views

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'...
3
votes
1answer
800 views

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 - ...
1
vote
1answer
1k views

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 ...
2
votes
1answer
240 views

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 ...
2
votes
1answer
215 views

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 ...
1
vote
1answer
130 views

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 ...
1
vote
1answer
100 views

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. ...
0
votes
1answer
151 views

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 ...
0
votes
1answer
35 views

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: ...