Category: Cryptography

Sharing secrets with polynomials

This post will present a couple ways to share secrets using polynomials. We have a group of n people who want to share a secret between them so that k of them will have to cooperate in order to unlock the secret. For example, maybe a committee of n = 5 wants to require the cooperation of […]

Regression, modular arithmetic, and PQC

Linear regression Suppose you have a linear regression with a couple predictors and no intercept term: β1×1 + β2×2 = y + ε where the x‘s are inputs, the β are fixed but unknown, y is the output, and ε is random error. Given n observations (x1, x2, y + ε), linear regression estimates the parameters β1 […]

What is an elliptic curve?

Elliptic curves are pure and applied, concrete and abstract, simple and complex. Elliptic curves have been studied for many years by pure mathematicians with no intention to apply the results to anything outside math itself. And yet elliptic curves have become a critical part of applied cryptography. Elliptic curves are very concrete. There are some […]

Microsoft replacing SHA-1

According to this article, Microsoft is patching Windows 7 and Windows Server 2008 to look for SHA-2 hash functions of updates. These older versions of Windows have been using SHA-1, while newer version are already using SHA-2. This is a good move, but unnecessary. Here’s what I mean by that. The update was likely unnecessary […]

Hash function menagerie

Here’s an oversimplified survey of cryptographic hash functions: Everyone used to use MD5, now they use some variation on SHA. There’s some truth to that. MD5 was very popular, and remains popular years after it was proven insecure. And now variations on SHA like SHA1 and SHA256 are commonly used. But there are a lot […]

Addition on Curve1174

I’ve written about elliptic curve and alluded to the fact that there’s a special kind of addition for points on the curve. But I haven’t gone into details because it’s more complicated than I wanted to get into. However, there’s a special case where the details are not complicated, the so called Edwards curves. I’ll look […]

Naming elliptic curves for cryptography

There are an infinite number of elliptic curves, but a small number that are used in cryptography, and these special curves have names. Apparently there are no hard and fast rules for how the names are chosen, but there are patterns. The named elliptic curves are over a prime field, i.e. a finite field with […]

RSA implementation flaws

Implementation flaws in RSA encryption make it less secure in practice than in theory. RSA encryption depends on 5 numbers: Large primes p and q The modulus n = pq Encryption key e Decryption key d The numbers p, q, and d are kept secret, and the numbers e and n are made public. The encryption method relies on the assumption that in practice one cannot […]

Economics, power laws, and hacking

Increasing costs impact some players more than others. Those who know about power laws and know how to prioritize are impacted less than those who naively believe everything is equally important. This post will look at economics and power laws in the context of password cracking. Increasing the cost of verifying a password does not […]

Salting and stretching a password

This post will look at a progression of ways to store passwords, from naive to sophisticated. Most naive: clear text Storing passwords in plain text is least secure thing a server could do. If this list is leaked, someone knows all the passwords with no effort. Better: hash values A better approach would be to […]

Reversing an MD5 hash

The MD5 hashing algorithm was once considered secure cryptographic hash, but those days are long gone [1]. For a given hash value, it doesn’t take much computing power to create a document with the same hash. Hash functions are not reversible in general. MD5 is a 128-bit hash, and so it maps any string, no […]

the beauty of maths in computer science [book review]

CRC Press sent me this book for review in CHANCE: Written by Jun Wu, “staff research scientist in Google who invented Google’s Chinese, Japanese, and Korean Web search algorithms”, and translated from the Chinese, 数学之美, originating from Google blog entries. (Meaning most references are pre-2010.) A large part of the book is about word processing and […]

How fast can you multiply really big numbers?

How long does it take to multiply very large integers? Using the algorithm you learned in elementary school, it takes O(n²) operations to multiply two n digit numbers. But for large enough numbers it pays to carry out multiplication very differently, using FFTs. If you’re multiplying integers with tens of thousands of decimal digits, the […]

Nature Outlook on AI

The 29 November 2018 issue of Nature had a series of papers on AIs (in its Outlook section). At the general public (awareness) level than in-depth machine-learning article. Including one on the forecasted consequences of ever-growing automation on jobs, quoting from a 2013 paper by Carl Frey and Michael Osborne [of probabilistic numerics fame!] that […]

RSA with one shared prime

The RSA encryption setup begins by finding two large prime numbers. These numbers are kept secret, but their product is made public. We discuss below just how difficult it is to recover two large primes from knowing their product. Suppose two people share one prime. That is, one person chooses primes p and q and the other chooses p […]

RSA with Pseudoprimes

RSA setup Recall the setup for RSA encryption given in the previous post. Select two very large prime numbers p and q. Compute n = pq and φ(n) = (p – 1)(q – 1). Choose an encryption key e relatively prime to φ(n). Calculate the decryption key d such that ed = 1 (mod φ(n)). Publish e and n, and keep d, p, and q secret. φ is Euler’s totient function, defined here. There’s a complication in the first […]

RSA encryption exponents are mostly all the same

The big idea of public key cryptography is that it lets you publish an encryption key e without compromising your decryption key d. A somewhat surprising detail of RSA public key cryptography is that in practice e is nearly always the same number, specifically e = 65537. We will review RSA, explain how this default e was chosen, and discuss why […]