Author: John

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

The hard part in becoming a command line wizard

I’ve long been impressed by shell one-liners. They seem like magical incantations. Pipe a few terse commands together, et voilà! Out pops the solution to a problem that would seem to require pages of code. Are these one-liners real or mythology? To some extent, they’re both. Below I’ll give a famous real example. Then I’ll argue […]

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

Twitter account for data privacy

I’ve started a new Twitter account for data privacy and related topics.
Twitter gave me the handle @data_tip even though that’s not what I typed in, and what I typed in is not being used. Apparently they don’t let you pick your handle…

Dose finding != dose escalation

You’ll often hear Phase I dose-finding trials referred to as dose escalation studies. This is because simple dose-finding methods can only explore in one direction: they can only escalate. Three-plus-three rule The most common dose finding method is the 3+3 rule. There are countless variations on this theme, but the basic idea is that you give […]

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

Supercookies

Supercookies, also known as evercookies or zombie cookies, are like browser cookies in that they can be used to track you, but are much harder to remove. What is a supercookie? The way I first heard supercookies describe was as a cookie that you can appear to delete, but as soon as you do, software […]

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

Normal approximation to Laplace distribution?

I heard the phrase “normal approximation to the Laplace distribution” recently and did a double take. The normal distribution does not approximate the Laplace! Normal and Laplace distributions A normal distribution has the familiar bell curve shape. A Laplace distribution, also known as a double exponential distribution, it pointed in the middle, like a pole […]

Probabilisitic Identifiers in CCPA

The CCPA, the California Privacy Protection Act, was passed last year and goes into effect at the beginning of next year. And just as the GDPR impacts businesses outside Europe, the CCPA will impact businesses outside California. The law specifically mentions probabilistic identifiers. “Probabilistic identifier” means the identification of a consumer or a device to a […]

Font Fingerprinting

Web sites may not be able to identify you, but they can probably identify your web browser. Your browser sends a lot of information back to web servers, and the combination of settings for a particular browser are usually unique. To get an idea what information we’re talking about, you could take a look at […]

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