meta user
network profile
| bio | website | isplab.tudelft.nl/users/… |
|---|---|---|
| location | Delft, Netherlands | |
| age | 27 | |
| visits | member for | 1 year, 1 month |
| seen | Jun 5 at 12:24 | |
| stats | profile views | 4 |
Scientific programmer at TU Delft
|
May 14 |
asked | DGK Cryptosystem Encryption Speedup |
|
May 9 |
comment |
Chinese Remainder Theorem and RSA Thank you very much. I can see that your knowledge of this subject is really good, but I am looking in 2 distinct books at the formulation of the CRT and I am failing to see how this simple statement that you presented above derives from it. The CRT states that a solution for a system of r linear congruences exists and is unique modulo n, where $n = \prod_{i=0}^rn_i$, but how do you use this? The "General Case" on Wikipedia doesn't help: en.wikipedia.org/wiki/Chinese_remainder_theorem#General_case |
|
May 9 |
awarded | Supporter |
|
May 9 |
accepted | Chinese Remainder Theorem and RSA |
|
May 9 |
comment |
Chinese Remainder Theorem and RSA That's a really nice and detailed proof, but I need more help to understand it: First, how did you end up with this formula: $M_1 = (M^d \bmod N) \bmod p = ((M \bmod p)^{d \mod p-1}) \bmod p$? Could you please detail it? I don't understand how you applied Fermat's "Little" Theorem to obtain it. It's clear how you've proven the formulae for the recombination step, but I'm not able to understand how does the CRT work in this case. How do you "immediately deduce that" $m = (M^d \bmod N) \mod pq$? |
|
May 9 |
comment |
Chinese Remainder Theorem and RSA @Ninefingers: Yes, I know, it's just that comments don't show previews and, anyway, I'll try to use it next time. Thanks. |
|
May 9 |
revised |
Chinese Remainder Theorem and RSA added 15 characters in body |
|
May 9 |
comment |
Chinese Remainder Theorem and RSA It's not clear to me how the CRT is applied to derive this formula: m = m_2 + (h * q), where h = q_inv * (m_1 - m_2) (mod p). I would really appreciate it if you could detail this procedure. |
|
May 9 |
awarded | Editor |
|
May 9 |
revised |
Chinese Remainder Theorem and RSA added 105 characters in body |
|
May 9 |
comment |
Chinese Remainder Theorem and RSA @mikeazo: The security update is not relevant for this conversation at the moment. If I manage to understand the way the CRT is applied for RSA, then I should be able to figure the rest out by myself, because it is similar. Please ignore my reference to DGK for now. |
|
May 9 |
asked | Chinese Remainder Theorem and RSA |
|
May 4 |
awarded | Student |
|
May 3 |
awarded | Scholar |
|
May 3 |
awarded | Analytical |
|
May 3 |
accepted | Generating Random Primes |
|
May 3 |
comment |
Generating Random Primes Now this is a really good answer. Thanks for taking the time to provide such a detailed explanation. It really clarifies the issue. I will probably go with the heuristic method, since it saves me some headache. There shouldn't be any performance concern at the moment, since prime numbers are required only for key generation, which I don't have to perform many times. |
|
May 3 |
asked | Generating Random Primes |
|
Apr 24 |
awarded | Autobiographer |
