October 28, 2012

Shor's algorithm and Quantum Fourier Transform

This post assumes you have a sound understanding of Quantum Mechanics, more precisely eigenstates,¬†superpositions and entanglements Shor’s algorithm allows us to find a factor of any composite number $$N$$ in $$O((log\ N)^2 (\ log^k\ (log\ N)^2))$$ for any random $$k$$, which is important in this scope to understand, as cryptography’s security baseline is founded on the fact that factoring cannot happen in polynomial time - I have talked on this subject in my post Yes Diffie-Hellman is secure, quoting myself ... Read more

October 31, 2011

Yes Diffie-Hellman is secure

When it comes to the Diffie-Hellman algorithm, there seem to be many confusions from newbies in¬†Cryptography as to whether an attacker could easily recompute the shared key by intercepting the prime numbers + public keys. While the answer is “no”, understanding why, requires an understanding the discrete logarithm problem. So here we go. ###Discrete Logarithm Problem### The discrete logarithm problem can be summarized as follow: Given $$a, b \in \mathbb{Z}/p\mathbb{Z} \wedge P$$ a prime, compute $$\log_b a$$ ... Read more