Mihai Todor
Reputation
230
Top tag
Next privilege 250 Rep.
 Jun 15 answered DGK Cryptosystem Key Generation and Decryption Issues May 21 comment How were the number of rounds for different key sizes of AES selected? Maybe this article provides some explanations: research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf The math behind the attacks that are detailed in the paper is a bit too much for me, though. May 21 asked DGK Cryptosystem Key Generation and Decryption Issues May 21 revised DGK Cryptosystem Encryption Speedup Made a small corection to the decryption formula... May 19 awarded Teacher May 18 revised DGK Cryptosystem Encryption Speedup Added a small clarification regarding the decryption procedure. May 18 accepted DGK Cryptosystem Encryption Speedup May 15 answered DGK Cryptosystem Encryption Speedup May 15 revised DGK Cryptosystem Encryption Speedup Corrected a formula. May 14 comment DGK Cryptosystem Encryption Speedup That is a very good remark, @poncho. Let me try to explain the motivation: This is supposed to be a building block used for comparing private inputs. Alice will generate the keys, encrypt data with the public key and send ciphertexts to Bob, who performs homomorphic operations on them and then sends the results back to Alice. I'm working in the semi-honest model, so it is assumed that both parties are honest but curious and they follow the protocol no matter what. Now, this allows Alice to use parts of the private key for speeding up the encryption process, since Bob will not encrypt anything. 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