Month: May 2019

R with Conda

Posted on by John

I’ve been unable to get some R libraries to install on my Linux laptop. Two libraries in particular were tseries and tidyverse. The same libraries installed just fine on Windows. (Maybe you need to install Rtools first before installing these on Windows; I don’t remember.)

I use conda all the time with Python, but I hadn’t tried it with R until this evening. Apparently it just works. The libraries I was trying to install have a lot of dependencies, and conda is very good at managing dependencies.

I removed my installation of R and reinstalled from conda:

    conda install r-base

Then I installed tseries with

    conda install r-tseries

and installed tidyverse analogously: 

    conda install r-tidyverse

Just prepend r- to the name of the R library you want to install.

I haven’t used it in anger yet, but it seems that everything works just fine.

On this day

Posted on by John

This morning as a sort of experiment I decided to look back at all my blog posts written on May 30 each year. There’s nothing special about this date, so I thought it might give an eclectic cross section of things I’ve written about.

***

Last year on this day I wrote about Calendars and continued fractions, based on a connection between the two topics I found in the book Calendrical Calculations.

***

Two years ago on this day I wrote about Color theory questions. I’ve been interested in color theory off and on for a while. At one point I thought I might “get to the bottom” of it and figure everything out to my satisfaction. I’ve since decided that color theory is a bottomless well: there’s no getting to the bottom of it. I might pick it back up some day with the more modest goal of learning a little more than I currently know.

***

I didn’t write a post on May 30 in 2014, 2015, or 2016.

***

On this day in 2013, I wrote a riff on a quote from Matt Briggs to the effect that there are no outliers, only measurements that don’t fit with your theory.

***

In 2012 on this day I posted Writing software for someone else. Most of what I’ve read about software development does not make the distinction between writing software for yourself and writing software for someone else, or at least does not emphasize the distinction.

When computer science students become professional programmers, they have to learn empathy. Or at least ideally they learn empathy. They go from completing homework assignments to writing programs that other people will work on and that other people will use. They learn “best practices,” best in this new context.

I made the opposite transition a few months after writing that post when I left MD Anderson Cancer Center to go out on my own. It took a while for me to decide what works best for me, mostly writing software for my own use. Sometimes I deliver software to clients, but more often I deliver reports that require me to write software that the client isn’t directly interested in.

***

My post for May 30, 2011 was just a quote from Richard Feynman speculating that in the long run, the development of Maxwell’s equations will be seen as the most important event of the 19th century.

***

In 2010 on this day I posted a quote from Paul Buchheit about the effect of suddenly acquiring wealth. For most people it would not be a good thing.

***

The post for May 30 in 2009 was called Killing too much of a tumor. You can actually make a tumor more harmful by killing off portions that were suppressing its growth. Reminds me now of how in war you want to leave enough of the enemy’s command intact that they have the ability to surrender.

***

Finally, on this day in 2008 I announced that I’d started a website at reproducibleresearch.org. I later gave the URL to people who had started a similar site with the same name, but ending in .org.

Promoting reproducible research seemed like a somewhat quixotic project at the time, but fortunately it has gained traction since then.

***

Is there a common theme in these posts? They are all about things that interest me, but that’s necessarily the case since they’re on my blog. One thing that surprises me is that the posts are not particularly mathematical. I would have expected that a quasi-random sample of posts would have turned up more math. But I did write about cancer and software development more when I worked in a cancer center and managed software developers.

Sum of all Spheres

Posted on by John

I ran across a video this afternoon that explains that the sum of volumes of all even-dimensional unit spheres equals eπ.

Why is that? Define vol(n) to be the volume of the unit sphere in dimension n. Then

\mathrm{vol}(n) = \frac{\pi^{n/2}}{\Gamma\left(\frac{n}{2} + 1\right)}

and so the sum of the volumes of all even dimensional spheres is

\sum_{k=0}^\infty \mathrm{vol}(2k) = \sum_{k=0}^\infty \frac{\pi^k}{k!} = \exp(\pi)

But what if you wanted to sum the volumes of all odd dimensional unit spheres? Or all dimensions, even and odd?

The answers to all these questions are easy in terms of the Mittag-Leffler function that I blogged about a while back. This function is defined as

E_{\alpha, \beta}(x) = \sum_{k=0}^\infty \frac{x^k}{\Gamma(\alpha k+\beta)}

and reduces to the exponential function when α = β = 1.

The sum of the volumes of all unit spheres of all dimensions is E1/2, 1(√π). And from the post mentioned above,

E_{1/2, 1}(x) = \exp(x^2) \, \mbox{erfc}(-x)

where erfc is the complementary error function. So the sum of all volumes of spheres is exp(π) erfc(-√π).

Now erfc(-√π) ≈ 1.9878 and so this says the sum of the volumes of spheres of all dimensions is about twice the sum of the even dimensional spheres alone. And so the sum of the odd dimensional unit sphere volumes is almost the same as the sum of the even dimensional ones.

By the way, you could easily answer other questions about sums of sphere volumes in terms of the Mittag-Leffler function. For example, if you want to add up the volumes in all dimensions that are a multiple of 3, you get E3/2, 1(π3/2).

Related posts

Inside the AES S-box

Posted on by John

black 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 designers [2], an invertible nonlinear transformation that works on 8 bits at a time.

There are 256 = 16 × 16 possible 8-bit numbers, and so the S-box can be represented as a 16 by 16 table mapping inputs to outputs. You can find the tables representing the S-box and its inverse in this text file in org-mode format.

This post will look in detail at how the entries of that table are filled. A high-level description of the design is as follows. For an 8-bit number x,

  1. Invert in GF(28)
  2. Multiply by a matrix L
  3. Add a constant c.

Next we dive into what each of these steps mean. And at the end we’ll work an example in detail.

My source is The Block Cipher Companion by Knudsen and Robshaw.

Inversion in GF(28)

Steps 1 and 3 take the inverse of a number as a member of the finite field GF(28), a finite field with 28 elements.

The number of elements in a finite field determines the field, up to isomorphism. That is, in a sense there is only one field with 28 = 256 elements. In fact there are many different fields with 256 elements. These fields are isomorphic, but when we’re doing actual calculations, rather than abstract theory, we need to specify which representation we’re using.

Finite fields can be specified as polynomials modulo an irreducible polynomial. To carry out our calculations we need to specify a particular irreducible 8th degree polynomial with binary coefficients. The one that AES uses is

p(x) = x8 + x4 + x3 + x + 1.

So by taking the inverse in GF(28) we mean to take an 8-bit number y, interpret it as a polynomial with binary coefficients, and find another 8-bit number x−1 such that when we multiply them as polynomials, and take the remainder after dividing by p(x) we get the polynomial 1.

There’s one wrinkle in this procedure: only 255 of the 256 elements of GF(28) have an inverse. There is no inverse for 0, but for our purposes we’ll take the inverse of 0 to be 0.

Multiplication by L

The matrix L we need here is the 8 by 8 binary matrix whose entries are

        10001111
        11000111
        11100011
        11110001
        11111000
        01111100
        00111110
        00011111

When we say to multiply x−1 by L we mean to think of x−1 as a vector over the field of two elements, and carry out matrix multiplication in that context.

Additive constant

The constant that we add is 0x63. The reason an additive constant was chosen was so that a zero input would not map to a zero output. Note that “addition” here is vector addition, and is carried out over the field of two elements, just as the multiplication above. This amounts to XOR of the bits.

Manual calculation example

To make everything above more concrete, we’ll calculate one entry of the table by hand.

Lets start with input y = 0x11 = 0b10001. We represent y as the polynomial f(x) = x4 + 1 and look for a polynomial g(x) such that the remainder when f(x) g(x) is divided by p(x) defined above is 1.

The process of finding g is complicated—maybe I’ll blog about it in the future—but I claim

g(x) = x7 + x5 + x4 + x2

which means the inverse of y in GF(28), represented in binary, is 0b10110100 = 0xB4. You can find a table of inverses here.

Next we multiply the matrix L by the vector made from the bits of y−1. However, there is a gotcha here. When Knudsen and Robshaw say to multiply the bits of y−1 by L, they assume the bits are arranged from least significant to most significant. Since the bits of y−1 are 10110100, we multiply L by the vector

[0, 0, 1, 0, 1, 1, 0, 1].

This multiplication gives us the vector

[1, 0, 0, 0, 0, 1, 1, 1].

Next we add the vector formed from the bits of 0x63, again from least significant to most significant. That means we lay out 0x63 = 0b01100011 as

[1, 1, 0, 0, 0, 1, 1, 0].

This gives us the result

[0, 1, 0, 0, 0, 0, 0, 1].

Reading the bits from least significant to most, this gives 0x82.

In sum, we’ve verified that the AES S-box takes 0x11 to 0x82, as stated in the table.

Related posts

[1] The Rijndael block cipher operates on blocks whose size is a multiple of 32 bits. The AES standard adopted Rijndael with block sizes 128, 192, and 256.

[2] “Rijndael” is a play on the designers of the cipher, Vincent Rijmen and Joan Daemen.

Random sampling from a file

Posted on by John

I recently learned about the Linux command line utility shuf from browsing The Art of Command Line. This could be useful for random sampling.

Given just a file name, shuf randomly permutes the lines of the file.

With the option -n you can specify how many lines to return. So it’s doing sampling without replacement. For example,

    shuf -n 10 foo.txt

would select 10 lines from foo.txt.

Actually, it would select at most 10 lines. You can’t select 10 lines without replacement from a file with less than 10 lines. If you ask for an impossible number of lines, the -n option is ignored.

You can also sample with replacement using the -r option. In that case you can select more lines than are in the file since lines may be reused. For example, you could run

    shuf -r -n 10 foo.txt

to select 10 lines drawn with replacement from foo.txt, regardless of how many lines foo.txt has. For example, when I ran the command above on a file containing

    alpha
    beta
    gamma

I got the output

    beta
    gamma
    gamma
    beta
    alpha
    alpha
    gamma
    gamma
    beta

I don’t know how shuf seeds its random generator. Maybe from the system time. But if you run it twice you will get different results. Probably.

Related

Between now and quantum

Posted on by John

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 do in the mean time [1]. Last year the agency replaced its Suite B cryptography recommendations with the CNSA: Commercial National Security Algorithm Suite.

In a nutshell: use well-established methods for now but with longer keys.

In a little larger nutshell, the recommendations are:

  • SHA-384 for secure hashing
  • AES-256 for symmetric encryption
  • RSA with 3072 bit keys for digital signatures and for key exchange
  • Diffie Hellman (DH) with 3072 bit keys for key exchange
  • Elliptic curve P-384, both for key exchange (ECDH) and for digital signatures (ECDSA)

Each of these represents a 50% or 100% increase in key length:

  • from 128 to 256 for AES
  • from 256 to 384 for hashing and ECC
  • from 2048 to 3072 for RSA and DH.

If these are just stopgap measures, why not jump straight to quantum-resistant methods? There are quantum-resistant encryption methods available, but most of them haven’t been studied that long. As Koblitz and Menezes put it,

… most quantum-resistant systems that have been proposed are complicated, have criteria for parameter selection that are not completely clear, and in some cases (such as NTRU) have a history of successful attacks on earlier versions.

Some methods do have a long history but have other drawbacks. Robert McEliece’s encryption method, for example, dates back to 1978 and has held up well, but it requires a megabyte key to achieve 128-bit security. There is a variation on McEliece’s method that has radically smaller keys, but it’s only been around for six years. In short, the dust hasn’t settled regarding post-quantum encryption methods.

Related posts

[1] People are naturally suspicious of algorithm recommendations coming from the NSA. Wouldn’t the agency like for everyone to use encryption methods that it could break? Of course. But the agency also wants US companies and government agencies to use encryption methods that foreign agencies cannot break.

There’s little downside to using established methods with longer keys. However, key length may not the weakest link. If you’re vulnerable to timing attacks, for example, doubling your key length may create a false sense of security.

Cosmic rays flipping bits

Posted on by John

cosmic ray

A cosmic ray striking computer memory at just the right time can flip a bit, turning a 0 into a 1 or vice versa. While I knew that cosmic ray bit flips were a theoretical possibility, I didn’t know until recently that there had been documented instances on the ground [1].

Radiolab did an episode on the case of a cosmic bit flip changing the vote tally in a Belgian election in 2003. The error was caught because one candidate got more votes than was logically possible. A recount showed that the person in question got 4096 more votes in the first count than the second count. The difference of exactly 212 votes was a clue that there had been a bit flip. All the other counts remained unchanged when they reran the tally.

It’s interesting that the cosmic ray-induced error was discovered presumably because the software quality was high. All software is subject to cosmic bit flipping, but most of it is so buggy that you couldn’t rule out other sources of error.

Cosmic bit flipping is becoming more common because processors have become smaller and more energy efficient: the less energy it takes for a program to set a bit intentionally, the less energy it takes for radiation to set a bit accidentally.

Related post: Six sigma events

[1] Spacecraft are especially susceptible to bit flipping from cosmic rays because they are out from under the radiation shield we enjoy on Earth’s surface.

Strong primes

Posted on by John

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 whose products are likely to be hard to factor. More specifically, though still not too specific, p is a strong prime if

  1. p is large
  2. p − 1 has a large prime factor q
  3. q − 1 has a large prime factor r
  4. p + 1 has a large prime factor s

The meaning of “large” is not precise, and varies over time. In (1), large means large enough that it is suitable for use in cryptography, such as in RSA encryption. This standard increases over time due to increases in computational power and improvements in factoring technology. The meaning of “large” in (2), (3), and (4) is not precise, but makes sense in relative terms. For example in (2), the smaller the ratio (p − 1)/q the better.

Relation between the definitions

The Wikipedia article on strong primes makes the following claim without any details:

A computationally large safe prime is likely to be a cryptographically strong prime.

I don’t know whether this has been proven, or even if it’s true, but I’d like to explore it empirically. (Update: see the section on safe primes below. I misread “safe” above as “strong.” Just as well: it lead to an interesting investigation.)

We’ll need some way to quantify whether a prime is strong in the cryptographic sense. This has probably been done before, but for my purposes I’ll use the sum of the logarithms of q, r, and s. We should look at these relative to the size of p, but all the p‘s I generate will be roughly the same size.

Python code

I’ll generate 100-bit primes just so my script will run quickly. These primes are too small for use in practice, but hopefully the results here will be representative of larger primes.

    from sympy import nextprime, prevprime, factorint, randprime
    import numpy as np
    
    # largest prime factor
    def lpf(n):
        return max(factorint(n).keys())
    
    def log2(n):
        np.log2(float(n))
    
    num_samples = 100
    data = np.zeros((num_samples, 5))
    
    bitsize = 100
    
    for i in range(num_samples):
        p = randprime(2**bitsize, 2**(bitsize+1))
        data[i,0] = 2*p > nextprime(p) + prevprime(p)
        q = lpf(p-1)
        r = lpf(q-1)
        s = lpf(p+1)
        data[i,1] = log2(q)
        data[i,2] = log2(r)
        data[i,3] = log2(s)
        data[i,4] = log2(q*r*s)

The columns of our matrix correspond to whether the prime is strong in the number theory sense, the number of bits in q, r, and s, and the total bits in the three numbers. (Technically the log base 2 rather than the number of bits.)

Results

There were 75 strong primes and 25 non-strong primes. Here were the averages:

    |-----+--------+------------|
    |     | strong | not strong |
    |-----+--------+------------|
    | q   |   63.6 |       58.8 |
    | r   |   41.2 |       37.0 |
    | s   |   66.3 |       64.3 |
    | sum |  171.0 |      160.1 |
    |-----+--------+------------|

The numbers are consistently higher for strong primes. However, the differences are small relative to the standard deviations of the values. Here are the standard deviations:

    |-----+--------+------------|
    |     | strong | not strong |
    |-----+--------+------------|
    | q   |   20.7 |       15.6 |
    | r   |   19.8 |       12.3 |
    | s   |   18.7 |       19.9 |
    | sum |   30.8 |       41.9 |
    |-----+--------+------------|

Safe primes

I realized after publishing this post that the Wikipedia quote didn’t say what I thought it did. It said that safe primes are likely to be cryptographically strong primes. I misread that as strong primes. But the investigation above remains valid. It shows weak evidence that strong primes in the number theoretical sense are also strong primes in the cryptographic sense.

Note that safe does not imply strong; it only implies the second criterion in the definition of strong. Also, strong does not imply safe.

To test empirically whether safe primes are likely to be cryptographically strong, I modified my code to generate safe primes and compute the strength as before, the sum of the logs base 2 of q, r, and s. We should expect the strength to be larger since the largest factor of p will always be as large as possible, (p − 1)/2. But there’s no obvious reason why r or s should be large.

For 100-bit safe primes, I got an average strength of 225.4 with standard deviation 22.8, much larger than in my first experiment, and with less variance.

Related posts

Unifiers and Diversifiers

Posted on by John

I saw a couple tweets this morning quoting Freeman Dyson’s book Infinite in All Directions.

Unifiers are people whose driving passion is to find general principles which will explain everything. They are happy if they can leave the universe looking a little simpler than they found it.

Diversifiers are people whose passion is to explore details. They are in love with the heterogeneity of nature … They are happy if they leave the universe a little more complicated than they found it.

Presumably these categories correspond to what Freeman elsewhere calls birds and frogs, or what others call hedgehogs and foxes. I imagine everyone takes pleasure in both unification and diversification, though in different proportions. Some are closer to one end of the spectrum than the other.

The scientific heroes presented to children are nearly always unifiers like Newton or Einstein [1]. You don’t see as many books celebrating, for example, a biologist who discovered that what was thought to be one species is really 37 different species. This creates an unrealistic picture of science since not many people discover grand unifying principles, though more find unifying principles on a small scale. I imagine many are discouraged from a career in science because they believe they have to be a unifier / bird / hedgehog, when in fact there are more openings for a diversifier / frog / fox.

Dyson may be taking a subtle swipe at unifiers by saying they want to leave the world looking a little simpler than they found it. There may be an unspoken accusation that unifiers create the illusion of unity by papering over diversity. True and significant unifying theories like general relativity are hard to come by. It’s much easier to come up with unifying theories that are incomplete or trivial.

Related posts

[1] Or at least scientists best known for their unifying work. Newton, for example, wasn’t entirely a unifier, but he’s best known for discovering unifying principles of gravity and motion.

Internet privacy as seen from 1975

Posted on by John

Science fiction authors set stories in the future, but they don’t necessarily try to predict the future, and so it’s a little odd to talk about what they “got right.” Getting something right implies they were making a prediction rather than imagining a setting of a story.

However, sometimes SF authors do indeed try to predict the future. This seems to have been at least somewhat the case with John Brunner and his 1975 novel The Shockwave Rider because he cites futurist Alvin Toffler in his acknowledgement.

… The Shockwave Rider derives in large part from Alvin Toffler’s stimulating study Future Shock, and in consequence I’m much obliged to him.

In light of Brunner’s hat tip to Toffler, I think it’s fair to talk about what he got right, or possibly what Toffler got right. Here’s a paragraph from the dust jacket that seemed prescient.

Webbed in a continental data-net that year by year draws tighter as more and still more information is fed to it, most people are apathetic, frightened, resigned to what ultimately will be a total abolishment of individual privacy. A whole new reason has been invented for paranoia: it is beyond doubt — whoever your are! — that someone, somewhere, knows something about you that you wanted to keep a secret … and you stand no chance of learning what it is.

The Shockwave Rider book cover

Related posts