Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 3 / 12G (Coding and Cryptography)

In the RSA cryptosystem, choose distinct large primes $p,q$, put $N=pq$, choose $e$ coprime to $\phi (N)=(p-1)(q-1)$, and choose $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. Publish $(N,e)$ and keep the factorization and $d$ private. Encrypt a properly encoded message $M$ as $C=M^e\mathrm{mod}N$ and decrypt as $M=C^d\mathrm{mod}N$. The Chinese remainder theorem proves correctness even for nonunits: modulo either prime, the message is either zero or satisfies Fermat's little theorem.

The public exponent $65537=2^{16}+1$ has few nonzero binary digits, so exponentiation needs only sixteen squarings and one extra multiplication. It is an efficient conventional choice, subject to the required coprimality and secure randomized message encoding. The same numerical choice for the private exponent would speed decryption, but for large moduli with balanced prime factors it is disastrously small: the continued-fraction attack on a small RSA private exponent recovers $d$ when, for example, $d<\frac{1}{3}{N}^{1/4}$ and $q<p<2q$. A small public exponent and a small private exponent have very different security implications.

To factor $N$ from $e,d$, write $ed-1=2^{s}t$ with $t$ odd. Choose random $a$ modulo $N$. If $\gcd (a,N)$ is nontrivial, factoring is already done. Otherwise compute $b=a^t$ and repeatedly square; the final value is one. If a value $x$ immediately preceding the first one is neither $1$ nor $-1$ modulo $N$, then $x^2\equiv 1(\mathrm{mod}N)$ andIndeed, the signs of $x$ modulo $p$ and $q$ differ. Restart if the chain begins at one or reaches $-1$ first. The Chinese remainder theorem makes the two prime components independent for a uniformly chosen unit. Their two-primary orders differ with probability at least one half: if the two exponents of two in $p-1,q-1$ are equal, the probability of equal orders is at most one half, and if unequal it is smaller. Since odd $t$ preserves these orders, this gives a randomized factoring procedure with bounded expected repetitions.

A bit commitment must be hiding before opening and binding after it. A concrete RSA construction uses a valid public RSA permutation whose inverse is unavailable to the receiver. Choose a random unit $x$ and a random bit vector $r$, and set $h(x,r)$ to their binary inner product modulo two. Send $y=x^e\mathrm{mod}N$, $r$, and $c=b\oplus h(x,r)$. To open, reveal $x$; the receiver checks $x^e=y$ and recovers $b=c\oplus h(x,r)$. Injectivity makes the opening bit unique. The hard-core predicate theorem applied to $(x,r)\mapsto (x^e,r)$ gives computational hiding under the RSA inversion assumption. The setup must ensure a valid modulus and exponent without giving the receiver the private exponent; otherwise hiding fails. Merely encrypting $0$ or $1$ would not hide a bit, since both ciphertexts could be computed publicly.