RSA encryption is based on the assumption that factoring large integers is hard. However, it’s possible that breaking RSA is easier than factoring. That is, the ability to factor large integers is sufficient for breaking RSA, but it might not be necessary. Two years after the publication of RSA, Michael Rabin created an alternative that […]
Category: Cryptography
on anonymisation
An article in the New York Times covering a recent publication in Nature Communications on the ability to identify 99.98% of Americans from almost any dataset with fifteen covariates. And mentioning the French approach of INSEE, more precisely CASD (a branch of GENES, as ENSAE and CREST to which I am affiliated), where my friend […]
Beating the odds on the Diffie-Hellman decision problem
There are a couple variations on the Diffie-Hellman problem in cryptography: the computation problem (CDH) and the decision problem (DDH). This post will explain both and give an example of where the former is hard and the latter easy. The Diffie-Hellman problems The Diffie-Hellman problems are formulated for an Abelian group. The main group we […]
Twisted elliptic curves
This morning I was sitting at a little bakery thinking about what to do before I check out of my hotel. I saw that the name of the bakery was Twist Bakery & Cafe, and that made me think of writing about twisted elliptic curves when I got back to my room. Twist of an […]
Homomorphic encryption
A function that satisfies f(x*y) = f(x)*f(y) is called a homomorphism. The symbol “*” can stand for any operation, and it need not stand for the same thing on both sides of the equation. Technically * is the group operation, and if the function f maps elements of one group to another, the group operation […]
Notes on computing hash functions
A secure hash function maps a file to a string of bits in a way that is hard to reverse. Ideally such a function has three properties: pre-image resistance collision resistance second pre-image resistance Pre-image resistance means that starting from the hash value, it is very difficult to infer what led to that output; it […]
Making public keys factorable with Rowhammer
The security of RSA encryption depends on the fact that the product of two large primes is difficult to factor. So if p and q are large primes, say 2048 bits each, then you can publish n = pq with little fear that someone can factor n to recover p and q. But if you […]
SQRL: Secure Quick Reliable Login
Steve Gibson’s Security Now is one of the podcasts I regularly listen to, and so I’ve been hearing him talk about his SQRL for a while. This week he finally released SQRL: Secure Quick Reliable Login. You can read more about SQRL in the white paper posted on the GRC web site. Here’s a tease […]
Using one RNG to sample another
Suppose you have two pseudorandom bit generators. They’re both fast, but not suitable for cryptographic use. How might you combine them into one generator that is suitable for cryptography? Coppersmith et al [1] had a simple but effective approach which they call the shrinking generator. The idea is to use one bit stream to sample […]
The AES S-box
The AES (Advanced Encryption Standard) algorithm takes in blocks of 128 or more bits [1] and applies a sequence of substitutions and permutations. The substitutions employ an “S-box”, named the Rijndael S-box after its designer, an invertible nonlinear transformation that works on 8 bits at a time. There are 256 = 16 × 16 possible […]
Between now and quantum
The National Security Agency has stated clearly that they believe this is the time to start moving to quantum-resistant encryption. Even the most optimistic enthusiasts for quantum computing believe that practical quantum computers are years away, but so is the standardization of post-quantum encryption methods. The NSA has also made some suggestions for what to […]
Strong primes
There are a couple different definitions of a strong prime. In number theory, a strong prime is one that is closer to the next prime than to the previous prime. For example, 11 is a strong prime because it is closer to 13 than to 7. In cryptography, a strong primes are roughly speaking primes […]
Goldilocks and the three multiplications
Mike Hamburg designed an elliptic curve he calls Ed448-Goldilocks. The prefix Ed refers to the fact that it’s an Edwards curve. The number 448 refers to the fact that the curve is over a prime field where the prime p has size 448 bits. But why Goldilocks? Golden primes and Goldilocks The prime in this […]
Tricks for arithmetic modulo NIST primes
The US National Institute of Standards and Technology (NIST) originally recommended 15 elliptic curves for use in elliptic curve cryptography [1]. Ten of these are over a field of size 2n. The other five are over prime fields. The sizes of these fields are known as the NIST primes. The NIST curves over prime fields […]
Elliptic curve P-384
The various elliptic curves used in ellitpic curve cryptography (ECC) have different properties, and we’ve looked at several of them before. For example, Curve25519 is implemented very efficiently, and the parameters were transparently chosen. Curve1174 is interesting because it’s an Edwards curve and has a special addition formula. This post looks at curve P-384. What’s […]
Isogeny-based encryption
If and when large quantum computers become practical, all currently widely deployed method for public key cryptography will break. Even the most optimistic proponents of quantum computing believe such computers are years away, maybe decades. But it also takes years, maybe decades, to develop, test, and deploy new encryption methods, and so researchers are working […]
Mixing error-correcting codes and cryptography
Secret codes and error-correcting codes have nothing to do with each other. Except when they do! Error-correcting codes Error correcting code make digital communication possible. Without some way to detect and correct errors, the corruption of a single bit could wreak havoc. A simple example of an error-detection code is check sums. A more sophisticated […]
Digital signatures with oil and vinegar
“Unbalanced oil and vinegar” is a colorful name for a cryptographic signature method. This post will give a high-level description of the method and explain where the name comes from. The RSA encryption algorithm depends on the fact that computers can easily multiply enormous numbers, but they cannot efficiently factor the product of two enormous […]
Efficient modular arithmetic technique for Curve25519
Daniel Bernstein’s Curve25519 is the elliptic curve y² = x³ + 486662x² + x over the prime field with order p = 2255 – 19. The curve is a popular choice in elliptic curve cryptography because its design choices are transparently justified [1] and because cryptography over the curve can be implemented very efficiently. This […]
An attack on RSA with exponent 3
As I noted in this post, RSA encryption is often carried out reusing exponents. Sometimes the exponent is exponent 3, which is subject to an attack we’ll describe below [1]. (The most common exponent is 65537.) Suppose the same message m is sent to three recipients and all three use exponent e = 3. Each […]