Posted by Jason Polak on 06. May 2018 · Write a comment · Categories: number-theory · Tags:

Alice wants her friends to send her stuff only she can read. RSA public-key encryption allows her to do that: she chooses huge primes $p$ and $q$ and releases $N = pq$ along with an encryption exponent $e$ such that ${\rm gcd}(e,(p-1)(q-1)) = 1$. If Bob wants to send Alice a message $m$, he sends $c = m^e$ modulo $N$ to Alice.

Computing $m$ from $m^e$ is hard if you only know $N$, but becomes easy with the prime factors $p$ and $q$. And, only Alice knows $p$ and $q$. The word “hard” is relative, and maybe someone will find an easy way to do it in the future, perhaps with quantum computers.

However, if you know $p$ and $q$, then you can compute $d$ such that $de = 1$ modulo $(p-1)(q-1)$. That is, you’re computing the inverse of $e$ in the multiplicative group $(\mathbb{Z}/N)^\times$. You can use Fermat’s little theorem: $x^{p-1} = 1$ in $\mathbb{Z}/p^\times$ for an $x\in (\mathbb{Z}/p)^\times$ to compute that $c^d = m^{ed} = m$ modulo $N$. Therefore, $c^d$ in $\mathbb{Z}/N$ is the decrypted message.
More »

Posted by Jason Polak on 30. April 2018 · Write a comment · Categories: number-theory · Tags:

Given a group $G$, and an element $g\in G$ (the “base”), the discrete logarithm $\log_g(h)$ of an $h\in G$ is an element $x\in G$ such that $g^x = h$ if it exists. Its name “discrete logarithm” essentially means that we are only allowed to use integer powers in the group, rather than extending the definition of exponentiation as with the usual logarithm for the real numbers.

Because of cryptographic applications, usually the discrete logarithm is seen in the world of finite fields or elliptic curves. Here, given a finite field $\F_q$, the discrete logarithm is considered in the multiplicative group $\F_q^\times$. It so happens that this group is cyclic, and hence it must be isomorphic to $\Z/(q-1)$. So, given a $g\in \F_q$ that generates $\F_q^\times$ as a multiplicative group, the discrete logarithm always exists and thus defines a function
$$\log_g: \F_q^\times\longrightarrow \Z/(q-1).$$
More »

Posted by Jason Polak on 01. March 2018 · Write a comment · Categories: book · Tags: ,

Today, public-key cryptography is everywhere, offering some measure of security for virtually all internet commerce transactions and secure shell connections. It’s hard to imagine life without it, even though most people aren’t aware of it.

Steven Levy’s Crypto is a great book to explain it and how it all came about. In fact, I first read it almost twenty years ago when I was in high school, and just read it again the other day.

How did encryption in the digital age start out? How did public-key cryptography get invented? And how did public-key crypto get into the hands of pretty much everyone with a web browser all over the world despite the attempts of the U.S. government to control it? These questions are answered in Levy’s book.
More »