Mihai Todor
Reputation
225
Top tag
Next privilege 250 Rep.
 Mar23 comment Generating Random Primes Well, I did get a really good answer here, so I can't complain. Also, my question was more about the general algorithmic approach of generating prime numbers. I used the libraries as mere examples. Jul23 comment Additive ElGamal cryptosystem using a finite field @PulpSpy Yes, that makes sense now. Thanks! Jul23 comment Additive ElGamal cryptosystem using a finite field Now this is an even nicer answer than Bristol's. Thank you very much @poncho. Too bad I can't give a +2. I'll leave his answer as accepted though, since he also provided a link to the python implementation. Jul23 comment Additive ElGamal cryptosystem using a finite field Thanks for taking the time to provide clear answers to all my questions and thank you very much for the python implementation link. May21 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. May14 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. May9 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 May9 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$? May9 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. May9 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. May9 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. May3 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.