Linked Questions
13 questions linked to/from Chinese Remainder Theorem and RSA
20
votes
4
answers
16k
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 ...
- 219
15
votes
2
answers
33k
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 ...
- 1,131
4
votes
1
answer
8k
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?
Gungun
2
votes
1
answer
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^{...
- 205
3
votes
1
answer
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'...
- 1,532
3
votes
1
answer
877
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 - ...
- 143
1
vote
1
answer
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 ...
- 493
2
votes
1
answer
265
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 ...
- 251
0
votes
1
answer
463
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:
...
2
votes
1
answer
350
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 ...
- 123
1
vote
1
answer
275
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 ...
- 25
1
vote
1
answer
289
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
...
- 183
1
vote
1
answer
118
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.
...
