Diffie Hellman Question
in [Cryptography]
|
Prev: Public & Private Key
Next: Encryption & Authentication
From: Joseph Ashwood on 27 Dec 2009 06:25 "Res" <res(a)pk.com> wrote in message news:hgq4rk$8k0$1(a)news.eternal-september.org... > It uses the following 5 words. > > Base, Power, Mod > Exp, Period. > > For A = G^a mod P > > Here, I think > A would be the Power. > G would be the Base > P would be the Mod > Exp would be 'a' - which we need to compute. That is correct, the second half of the page explains the terminology choices. > I don't get what's Period in the Applet. > I am trying to use the applet to break some DH numbers > I generated. > > My Generator G = 2 > My 10 byte Prime P = 1500450271 Less than 4 bytes, but it is prime, so the calculations will work. > My Random Number 'a' = 740441303 > My A = 2^276794800 mod 276794800 = 276794800 Equation for A isn't correct, but the final value for A is, probably just a typo. > > In the Applet, I enter > Base = 2 > Power = 276794800 > Mod = 1500450271 > > Now I click on "Find Discrete Logarithm", I get > Exp 240291213 > Period 250075045 > This just takes a fraction of a second. > > But how does this lead to 'a'? G^exp = G^a mod P, so exp and a are functionally the same. The period matter in this because k*period+exp = a for some integer k, in this case k=2. This happens because of additional subgroups of P which can be complicated to figure out completely. Joe
From: Res on 5 Jan 2010 06:10 "Joseph Ashwood" <ashwood(a)msn.com> wrote in message news:Y0IZm.11222$yM1.7988(a)newsfe11.iad... > "Res" <res(a)pk.com> wrote in message > news:hgq4rk$8k0$1(a)news.eternal-september.org... >> It uses the following 5 words. >> >> Base, Power, Mod >> Exp, Period. >> >> For A = G^a mod P >> >> Here, I think >> A would be the Power. >> G would be the Base >> P would be the Mod >> Exp would be 'a' - which we need to compute. > > That is correct, the second half of the page explains the terminology > choices. I couldn't find it - doesn't matter. > >> I don't get what's Period in the Applet. >> I am trying to use the applet to break some DH numbers >> I generated. >> >> My Generator G = 2 >> My 10 byte Prime P = 1500450271 > > Less than 4 bytes, but it is prime, so the calculations will work. Meant to write 10 digit prime. >> My Random Number 'a' = 740441303 >> My A = 2^276794800 mod 276794800 = 276794800 > > Equation for A isn't correct, but the final value for A is, probably just > a typo. Yes - copy/paste error. >> In the Applet, I enter >> Base = 2 >> Power = 276794800 >> Mod = 1500450271 >> >> Now I click on "Find Discrete Logarithm", I get >> Exp 240291213 >> Period 250075045 >> This just takes a fraction of a second. >> >> But how does this lead to 'a'? > > G^exp = G^a mod P, so exp and a are functionally the same. The period > matter in this because k*period+exp = a for some integer k, in this case > k=2. Super. That worked. Thanks very much for your detailed explanation!!! > > This happens because of additional subgroups of P which can be complicated > to figure out completely. > Joe
From: Res on 5 Jan 2010 06:12 Anyone else have a chance to look at this? http://groups.google.com/group/sci.crypt/msg/438469a0c163d6e6 http://bit.ly/5oCFtq - It looks like in his case also, the generator(g) & the prime(P) are hard-wired into the app. - In his case, the [(g**b) mod P] is also hard-wired into the application - will this reduce the security in a case - I would assume not, since this is a public key. Looking at his usecase, it doesn't look like he has any restrictions on the length of P like me - since he is truncating the license key anyway, he can have a big P - 2048 bit one like Joseph Ashwood suggested. - He is using the capabilities string padded with zeroes as the program's private key - i.e. he is using at as 'a' to generate his public key [(g**a) mod P]. But it looks like anyone can guess his 'a' because it's not really random - it's based on known capabilities strings. How does this affect the security? - How exactly can one derive a private key from a capabilities string - I assume it could be something like adding up the ascii values of each character of the string - or am I misunderstanding something here? - Joseph gave some respresentive numbers as to how much time it would take to break my original algorithm - 90 seconds, 5 minutes, 1 day etc. Likewise, what kind of time to break Eric Lee Green's algorithm assuming different sizes of the prime?
From: Joseph Ashwood on 6 Jan 2010 09:35
"Res" <res(a)pk.com> wrote in message news:hhv6ri$pks$1(a)news.eternal-september.org... > Anyone else have a chance to look at this? > > > http://groups.google.com/group/sci.crypt/msg/438469a0c163d6e6 > > http://bit.ly/5oCFtq > > - It looks like in his case also, the generator(g) & the prime(P) are > hard-wired into the app. > > - In his case, the [(g**b) mod P] is also hard-wired into the > application - > will this reduce the security in a case - I would assume not, since this > is > a public key. It prevents rolling over the key, but this is always a complex problem to solve anyway. In terms of security at any given time, it doesn't change it. > - Joseph gave some respresentive numbers as to how much time > it would take to break my original algorithm - 90 seconds, 5 minutes, > 1 day etc. Likewise, what kind of time to break Eric Lee Green's > algorithm assuming different sizes of the prime? Same times, its still the same algorithm. The only change would be that if the entropy of client private key is too low it may be guessable, but for the use case it won't matter. There is also the matter of if the final value is too small, probably also not a concern. For your situation it won't work though because you're transferring different data, so shortcutting a single transfer won't make things more possible. It does however bring up a few suggestions for your case. As someone observed (sorry I deleted your message already) there's really very little reason for you to use public key cryptography, but I'll keep it for sympathy. I will also explicitly state right now that this is not the strongest possible encryption, has a few assumptions to keep an eye on (hash functions), I also assume that the time portion we discussed before is strong. Assume both sides have the public key for the other. Both sides compute the shared secret SS. R is a stored counter message is M one time key OTK = SHA-512(SS | R) // | is append EncKey = first 256 bits of SHA-512(OTK | "Encryption Key") MACKey = first 256 bits of SHA-512(OTK | "Authentication Key") MAC = AES256-OMAC(MACKey, M) //AES256-OMAC(Key, Data) Encrypted = AES256-CBC(EncKey, MAC, M) //AES256-CBC(Key, IV, Data) Transfer = {R, MAC, Encrypted} R++ Alice's side should be fairly obvious but Alice checks R for validity (should be one over the last one, account for dropped messages as needed), computes OTK, EncKey, MACKey, decrypts to get M, checks MAC. Since R only needs to never repeat it should be fairly easy for you to determine the length necessary. This will have 128 bits + length( R ) overhead, which is about the minimum possible, securely. The choice of CBC instead of CTR is fairly non-obvious. I chose it because of two concerns. It concerns me that various EncKeys are not guarenteed fully independent, and for CTR to be secure would require that. The second concern is that IV is not carefully chosen so while the calculations are believed to be exceedingly complex I'm not convinced it will be properly covered by CTRs abilities, CTR requires a few considerations on the IV, normally these are easily achieved, but reducing the transfer space as much as possible doesn't allow for control over the IV, CBC has lower requirements on the IV so it makes more sense. Using CBC also allows the system to absorb a few mistakes in R where CTR would collapse quickly. As I said earlier you need to keep an eye on the hash, SHA-512 is a conservative choice, but any valid cryptographic questions about the security of SHA-512 and you should abandon it for the current greatest. There are also some concerns about AES, related keys have security issues, while the keys are independent enough, progress against AES will also require moving to a different cipher. These kinds of problems crop up any time it is necessary to bring some aspect of the system to the absolute minimum. The public key cryptography can be removed, although this can cause problems with key rollover situations. This works because no numbers change, the shared secret SS is always the same. If you can afford the computation time I'd recommend keeping it, there are subtle advantages that it gives you. Joe |