I’ve written about Base32 and Base64 encoding, and the less common Base58 encoding. For completeness I wanted to mention Base85 encoding, also known as Ascii85. Like Base64, the goal of Base85 encoding is to encode binary data printable ASCII characters. But it uses a larger set of characters, and so it can be a little […]

# Category: Math

## Base 58 encoding and Bitcoin addresses

A few weeks ago I wrote about base32 and base64 encoding. I’ll review these quickly then discuss base58 and its use in Bitcoin. Base32 and base64 All three methods have the goal of compactly representing large numbers while maintaining readability. Douglas Crockford’s base32 encoding is the most conservative: it’s case-insensitive and it does not use […]

## Implementing the ChaCha RNG in Python

My previous post talked about the ChaCha random number generator and how Google is using it in a stream cipher for encryption on low-end devices. This post talks about how to implement ChaCha in pure Python. First of all, the only reason to implement ChaCha in pure Python is to play with it. It would […]

## 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 […]

## Testing for primes less than a quintillion

The most common way to test whether a large number is prime is the Miller-Rabin test. If the test says a number is composite, it’s definitely composite. Otherwise the number is very likely, but not certain, to be prime. A pseudoprime is a composite number that slips past the Miller-Rabin test. (Actually, a strong pseudoprime. […]

## The point at infinity

As I explained in an earlier post, a first pass at the definition of an elliptic curve is the set of points satisfying y² = x³ + ax + b. There are a few things missing from this definition, as indicated before, one being the mysterious “point at infinity.” I gave a hand-waving explanation that […]

## 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 […]

## 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 […]

## Entropy extractor used in μRNG

Yesterday I mentioned μRNG, a true random number generator (TRNG) that takes physical sources of randomness as input. These sources are independent but non-uniform. This post will present the entropy extractor μRNG uses to take non-uniform bits as input and produce uniform bits as output. We will present Python code for playing with the entropy extractor. (μRNG […]

## Solving for probability given entropy

If a coin comes up heads with probability p and tails with probability 1-p, the entropy in the coin flip is S = –p log2 p – (1-p) log2 (1-p). It’s common to start with p and compute entropy, but recently I had to go the other way around: given entropy, solve for p. It’s easy to come up […]

## Missing information anxiety

A recurring theme in math is that you may not need to do what it looks like you need to do. There may be a shortcut to where you want to go. A special case of this is that you may not need all the information that you think you need. For example, if you […]

## Sum-product theorem for finite fields

A week ago I wrote about using some Python code to play with the sum-product theorem of Erdős and Szemerédi and its conjectured refinement. This morning I learned that the Erdős-Szemerédi theorem has been extended to finite fields. David Johnston left a comment saying that he and his colleagues used this extension to finite fields as […]

## Computing Legendre and Jacobi symbols

In a earlier post I introduce the Legendre symbol where a is a positive integer and p is prime. It is defined to be 0 if a is a multiple of p, 1 if a has a square root mod p, and -1 otherwise. The Jacobi symbol is a generalization of the Legendre symbol and uses the same notation. It […]

## 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 […]

## Exploring the sum-product conjecture

Quanta Magazine posted an article yesterday about the sum-product problem of Paul Erdős and Endre Szemerédi. This problem starts with a finite set of real numbers A then considers the size of the sets A+A and A*A. That is, if we add every element of A to every other element of A, how many distinct sums are there? If we […]

## Soviet license plates and Kolmogorov complexity

Physicist Lev Landau used to play a mental game with Soviet license plates [1]. The plates had the form of two digits, a dash, two more digits, and some letters. Rules of the game His game was to apply high school math operators to the numbers on both side of the dash so that the […]

## Soviet license plates and Kolmogorov complexity

Physicist Lev Landau used to play a mental game with Soviet license plates [1]. The plates had the form of two digits, a dash, two more digits, and some letters. Rules of the game His game was to apply high school math operators to the numbers on both side of the dash so that the […]

## 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 […]