Superconductor

Hasse's theorem

If we have an elliptic curve over GF(q)

y² = x³ + ax + b

then we should expect to have roughly q points on this curve.

In a finite field, roughly half of the elements have a square root, so if the cubic x³ + ax + b takes on values that are roughly representative of the entire field GF(q), then we should get a value that has a square root roughly half the time. Each of these values for x gives us two possible values for y, so we should expect about 2 x (q/2) = q points on such a curve.

It’s actually possible to prove that that has to be the case. If we write #E(GF(q)) for the number of points on an elliptic curve over GF(q), then Hasse’s theorem tells us that this is the case. It actually tells us that we have to have

-2√q ≤ #E(GF(q)) – (q + 1) ≤ 2√q

which we can also write as

q + 1 -2√q ≤ #E(GF(q))  ≤ q + 1 + 2√q

or

(√q - 1)² ≤ #E(GF(q)) ≤ (√q + 1)²

It's even possible to generalize Hasse’s theorem to hyperelliptic curves, where it turns out that the Jacobian of a curve of genus g over GF(q) has to have about q^g points^. This shouldn't be too surprising. If we think of the typical element of the Jacobian as

P = (P₁) + ... + (P_g) - g(O)

then we should expect about q ways to pick P₁, q ways to pick P₂, etc, for a total of q^g ways to pick P₁ through P_g.

It's even possible to show that for a hyperelliptic curve of genus g, we can put the following limits (the Hasse-Weil bound) on the size of the Jacobian #J(GF(q)):

(√q - 1)^2g ≤ #J(GF(q)) ≤ (√q + 1)^2g

This means that we can easily get a Jacobian that’s big enough to make it comparable in size to an elliptic curve group, and we can actually do this by using a value of q that’s smaller than we would need for the elliptic curve group.

On the other hand, while the best way to calculate discrete logs in an elliptic curve group is by using an algorithm like Pollard’s rho algorithm that doesn’t use the structure of the elliptic curve at all, there are ways to calculate discrete logs in the Jacobian of a hyperelliptic curve that are faster than Pollard’s rho algorithm. That doesn’t mean that hyperelliptic curves aren’t useful. It means that things just aren’t as good as we’d like them to be. Maybe that's a topic for a future post.

Variations in on-line prices

When you go to buy enterprise software, you never really expect to pay the list price. Businesses are now fairly good at manipulating software vendors, waiting until right before the end of the vendors' fiscal quarter or year, always waiting until they're ready to buy to get the "what if I commit to buy right now?" discount, etc. But things where there's really no way to negotiate prices, you expect prices to be set at what the business thinks that they can get for something. This is why I don't understand the prices of books that I see at various on-line stores.

When I went to Amazon.com just now to get some examples, I was surprised to find that prices advertised for the first book that I randomly picked ranged from a low of $16.47 to a high of almost $1,000. And that's for the same condition, etc. The next few books didn't have as dramatic a range, but the range was still surprisingly high: from $14.45 to $24.95 (a factor of 1.7 from low to high), from $18.95 to $87.56 (a factor of 4.6) and from $55 to $129.64 (a factor of  2.6).

Some people tell me that on-line book stores will often put a very high price on a particularly notable book just to advertise the fact that they have a copy, never expecting to actually sell it at that price. Apparently they think that this is an effective type of advertising. But with a book that lists for less that $20, I can't believe that that model works very well.

And if you're an on-line business who wants to set the prices for your books, wouldn't you check to see what the normal range of prices is for your books before setting your own prices? After all, if you set your prices higher than others have it's probably reasonable to assume that you are not going to sell your copy until all of the lower-priced alternatives have sold.

There's almost always a reasonable explanation for business' behavior, but it's not always obvious what that explanation is, and that's one of the big reasons that economists get paid to do what they do. Maybe this is the sort of thing that some economics graduate student can explain and write up in his dissertation.

Scoping software vs. writing

After you've been involved in software development for a while you get fairly good at estimating how long it will take to do various things - adding features, correcting bugs, etc. You tend to get better at this with practice. Curiously, I didn't have the quite same experience when it came to writing.

When your write things, you're often given an approximate number of words that the editor is looking for on a partiucular topic. Sometimes this can be fairly vague, like between 2,000 to 3,000 words. Sometimes you're given more precise requirements. One editor once asked for between 720 and 730 words on a particular topic, for example.

After a while you get a rough idea of how much detail you can fit into 500 words, 1,000 words, etc. But while you tend to to get better at scoping software development projects after not too long, I'm still sometimes way off from what I think needs to be written. I'll agree to write something like 2,000 words on a particular topic, for example, but after I think about the topic for a while I find that there's really not that much to say about it. (I'm actually trying to figure out how to stretch 500 words to 1,200 words right now...)

Maybe I just don't think the right way about writing yet.

RIVYERA from SciEngines

The clever engineers at SciEngines now have an off-the-shelf computer, the RIVYERA S3-5000, that will crack DES in roughly one day. In the unlikely event that you're a hacker who needs to recover DES keys, this is definitely how you'll want to do it. A RIVYERA is roughly 20 times more cost-effective than the EFF's dot-com era DES Cracker.

These RIVYERA machines use 128 Xilinx XC3S5000 FPGAs to get the ability to test 292 billion DES keys per second. That's very impressive. I haven't been involved in building computers for a while, but unless things have changed a lot, it's probably still pretty much like Tracy Kidder describes in The Soul of a New Machine, although I have to wonder if engineers still quit their jobs from the stress of making faster computers, leaving behind only a note that says "I'm going to a commune in Vermont and will deal with no unit of time shorter than a season."

In any case, I'd love to hear the engineers at SciEngines tell the story of how the RIVYERA came to be.

To put things in perspective, however, even at the rate that a RIVYERA S3-5000 can crack DES, cracking a 3DES key will take essentially forever - roughly 200 trillion years. So I doubt that we'll see anything capable of cracking a 3DES key any time soon.

Stand on Zanzibar

I just finished an interesting book, Stand on Zanzibar, by John Brunner. It's about a dystopian future in which the Earth's population grows to the point that governments take all sorts of extremely draconian measures to keep it in check. It was published in 1968 but is set in the year 2010, and it's interesting to see how accurate Brunner's predictions of the future were. Like in any other work of speculative fiction, he managed to get a few things right but he also got others totally wrong. In general, Brunner's vision of the year 2010 is very different from the real 2010. It may not be as different as George Orwell's vision of the year 1984 was from the real 1984, but it really didn't seem very close.

I also read this book because I managed to get a copy that was published in 2009 yet autographed by Brunner, who died in 1995. It seems that before he died he signed some signature pages for a book that never got published, and that the most recent publisher managed to get ahold of these and use them in their edition of Stand on Zanzibar.

It looked to me like Brunner totally missed the affects of IT on society. Or maybe he didn't. Brunner wrote Stand on Zanzibar to point out how overpopulation could end up being a problem. It wasn't meant to point out how the rise of IT could cause a dramatic decrease in privacy. I actually don't know of any books that focus on that particular angle, but I'd probably read one if someone wrote it.

I'm sure that it wouldn't be too hard to extrapolate from the dramatic loss of privacy that we've seen happen in the past decade to the point that it would make the basis for an interesting story. It's not clear to me, however, whether such a story would be better classified as science-fiction or as horror.

Elliptic curve point addition revisited

The usual way to add points on an elliptic curve uses the cord-and-tangent method. To add two points P and Q we draw the line through P and Q and find the third point where this line intersects the curve. We then reflect this point across the x-axis to get R = P + Q. This is shown in this picture, where we find that (-1,0) + (0,1) = (2,-3).

In this case, the point at infinity O acts like zero: P + O = P. It turns out that we don’t really need to use the point at infinity for zero, but if we don’t, the way that we add points changes slightly.

The picture above shows the elliptic curve

y = x³ + 1

The point Z = (0,-1) is on this curve, and we can define a way to add points on the curve in a way that this point acts like the zero element. Here’s how we do this. To add two points P and Q we draw the line through P and Q and find the third point where this line intersects the curve. We then draw the line through this point and Z and find the third point where this (second) line crosses the curve. We call this point R = P + Q. This is shown in this picture, where we find that (-1,0) + (0,1) = (2,3).

This picture is actually a bit tricky to follow. The line through (2,3) and Z actually touches the curve twice at (2,3), so the third point of intersection is also (2,3). (You even get this problem when you try to visualize the addition of points on this curve using the usual definition of addition, but I couldn’t think of an example that’s obviously better to use.)

In this case, the point at infinity doesn’t act like the zero element. If we add (2,3) to the point at infinity, for example, we find that the line between the two points intersects the curve at (2,-3). We then draw the line through (2,-3) and (0,-1) and find that it meets the curve at (-1,0), so we have that (2,3) + ∞ = (-1,0).

Showing that point addition with an arbitrary point acting as the zero element works out like we want to (associative and commutative) is actually fairly tedious, but it turns out to define a way that’s just as valid as the usual way, where we use the point at infinity for the zero element. (Come to think of it, showing that the usual version of point addition is associative and commutative is also fairly tedious, so this shouldn't really come as a surprise.)

It should also be clear that the usual form of point addition is really just a special case of the more general version. When we reflect a point across the x-axis, that's really the same as drawing a line through the finite point and the point at infinity and finding the third place where the line intersects the elliptic curve. This might be a case where it's useful to think of the point at infinity as the projective point (0,1,0), so that a line through the point at infinity is one that's parallel to the line x = 0. 

Elliptic curves and catastrophies

We usually think of elliptic curves of the form

y² = x³ + ax +b

What happens of we just look at the cubic part of an elliptic curve and think of it as an equation in a, b and x instead of just a polynomial in x?

It's even not too hard to draw a graph of that to see what it looks like. The first step is to use the cubic formula to write x as a function of a and b. Once we have that we can graph x = x(a,b) to see what's happening.

The cubic formula actually gives us three different roots:

 
   
  
Let's use the first of these because that looks like it's the most likely to give us a real number instead of a complex number and real numbers are easier to graph.

Using that for x, here's what you get when you graph x as a function of a and b:

 
The sudden discontinuity is actually just what we should expect because a cubic of the form x³ + ax is the very thing that causes a fold catastrophe, but until I made that graph I hadn't considered the connection between elliptic curves and catastrophe theory.

Monty Python meets Landauer's principle

Landauer's principle tells us that computations in which we erase bits always release energy. In a very simple case, for example, when two electrons go into an AND gate and only one comes out, the additional energy carried by the second electron has to go somewhere. Landauer’s argument was essentially that if the number of thermodynamic states is cut in half then the entropy is reduced by k log 2 per bit, which then gets reflected in the energy of k T log 2. Quantum computing, which is inherently reversible, is interesting, in part, because it lets you avoid the limitations of Landauer's principle.

It turns out that not everyone agrees with Landauer's analysis. "Logic and Entropy" by Orly Shenker argues that Landauer's analysis is flawed, for example. Papers like this one spurred others to write rebuttals. An example of this is "Notes on Landauer's Principle, Reversible Computation, and Maxwell's Demon" by Charles Bennett.

With my limited understanding of thermodynamics, Landauer's principle certainly looks reasonable to me, but I'm certainly not an expert and I can't say that I really understand either side of this argument. When I read papers like these, however, I'm often reminded of Monty Python's argument sketch in which there's an exchange roughly like this:

"Yes, it is!"

"No, it isn't!"

"Yes, it is!"

There just seems to be more math in the arguments over Landauer's principle.

Risk Assessment Methodologies: A Comparison

I came across another interesting report from the Burton Group. This one was "Risk Assessment Methodologies: A Comparison." Here's how they describe their findings:

Bottom Line: The operating phrase for using a risk assessment methodology is a “good starting point.” Enterprises will find value in the U.S. National Institute of Standards and Technology (NIST), Information Systems Audit and Control Association (ISACA), Information Security Forum (ISF), or Operationally Critical Threat, Asset, and Vulnerability Evaluation (OCTAVE) risk assessment frameworks, but each will need care and feeding for apt use. If system-level assessments are the goal, NIST and ISF are good bets. If enterprise-wide IT or information risk needs consideration, then ISACA's Risk IT should receive attention. OCTAVE's flexibility makes it good for a wide variety of uses, but it comes with some steep homework. Enterprises should choose a framework that correctly targets their assessment scope, complements their chosen control framework, and helps to socialize the risk assessment effort across the organization.

I've always been curious about how the various risk assessment methodologies would compare, and it really shouldn't be too surprising that each has its own particular strengths and weaknesses. After all, if one methodology was clearly better, it would probably end up being the only one used while people would lose interest in the others. So the fact that several methodologies exist is essentially proof that each has some area in which it excels, and this report seems to be a good summary of exactly what those areas are.

The next Key Management Summit

It looks like Terence Spies, the CTO of Voltage, will be the general chair of the next Key Management Summit. As soon as Terence gets a chance to get organized, we'll have a better idea of where and when the next event will be held.

Projective and affine elliptic curves

Suppose that we have an elliptic curve

y² = x³ + ax + b

When we embed this in the projective plane by the change of variables

x = X/Z

and

y = Y/X

we get the homogeneous equation

Y²Z = X³ + aXZ² + bZ³

When we do this, something interesting happens: we actually end up with two copies of the original elliptic curve.

If we set Z = 1 we get

Y² = X³ + aX + b

which is obviously a copy of the original curve.

If we set Y = 1 we get

Z = X³ + aXZ² + bZ³

That's not an obvious copy of the original curve, but if we make the change of variables

X = X/Z

and

Z = 1/Z

we get that

Z² = X³ + aX + b

which makes the other copy of the curve clearer. 

The bottom line is that we can think of the projective version of the curve as being essentially two copies of the affine version of the curve that are glued together.

Random thoughts on writing

The first time that you get something published, it’s great. You walk around thinking to yourself I’m a published author now. That’s incredibly cool. That feeling definitely makes it worth the time and effort that it takes. The next time, however, the coolness drops to roughly 70 percent of the first time, and this trend seems to continue for quite a while, so that each time you get something published is about 70 percent as cool as the previous time. 

Here’s a graph of what 0.7^x looks like:

 
So after the 15^th time or so that you get something published, essentially all of the coolness is gone – you’re down to less that one-half of one percent of the original level of coolness. At that point it’s just work.

So I’d guess the bottom line is that everyone should take the time and effort to get something published at least once, but don’t be surprised if your perspective on it changes after you’ve been doing it for a while. If this model's accurate, you might actually get tired of it fairly quickly.

Mercator's thoughts on EMV

In a previous post, I mentioned that when the UK rolled out EMV how card-not-present (CNP) fraud increased so much that the total amount of fraud actually increased instead of decreasing. Apparently the increase in CNP fraud isn’t limited to just the UK. Here’s what the Mercator Group said in their recent report “Encryption, Tokenization and the Top Tier Merchant: A Progress Report on PCI, Deployment and the Cost of Payment Security:”

CNP fraud rates in EMV countries have risen dramatically because of EMV’s effective protection against counterfeit cards. EMV does not address card not present (CNP) risk; it is one layer of security but hardly a blanket solution (there’s no such thing).

The summary of this report also proposes an interesting reality check on EMV:

There is plenty of misinformation swirling around tokenization, encryption and EMV. Some believe that all problems would be solved if only EMV were used in the US. If only that were true. Card number security requires layered defenses and that means using multiple techniques to limit counterfeit credentials (EMV) and to perform the Reverse Rumpelstiltskin of turning our digital gold into straw bits (encryption and tokenization).

There’s lots of other interesting information in this report, and it’s probably worth tracking down a copy if you’re interested in the business of protecting credit card information at large merchants.

An invention motivated by spam

There’s apparently a doctor out there with the same name as me. I say this because I often get requests for permission to reprint various medical articles as weall as spam from biomedical companies. One of these recent spams advertised a product that identifies proteins by using mass spectrometry.

That made me wonder if it would be possible to invent a device that could automate the identification of the books on my desk. Maybe this machine would burn one of these books and determine from the ash whether the content of the book was number theory, algebraic geometry, elliptic curves, etc. Such a machine, of course, would be called a "math spectrometer." 

Explaining the silence here

It looks like another big credit card processor has signed up to use Voltage's encryption technologies. This time it's Elavon, which means that three of the top five processors (Heartland, Fifth Third and Elavon) are now Voltage customers. Four of the top six POS vendors (Hypercom, Exadigm, UIC, XAC) are also.

This might explain why you don't actually see our sales guys in the office much. When they're not around it's much quieter and easier for the rest of us to work, so I certainly hope that their success in the payments industry continues.

Weighted projective coordinates

Homogeneous coordinates are the simplest way to embed an elliptic curve

y² = x³+ ax + b

into a projective space. To do this we write

x=X/Z

and

y=Y/Z

to get

Y²Z = X³ + aXZ² + bZ³

From this form of an elliptic curve, it's easy to see what projective point corresponds to the point at infinity on the affine curve. This is where the projective form of the curve meets Z = 0. This happens when X = 0, or at (0,Y,0). In homogeneous coordinates we identify (x,y,z) with (cx,cy,cz) so we can identify (0,Y,0) with (0,1,0) giving O = (0,1,0) as a simpler way to write the point O.

With weighted projective coordinates we identify (x,y,z) with (c^ux,c^vy,c^wz) in (u,v,w)-weighted projective coordinates. The most common example of this is probably Jacobian projective coordinates, which are (2,3,1)-weighted. To use Jacobian coordinates to embed the elliptic curve

y² = x³+ ax + b

into projective space we write

x = X/Z²

and

y = Y/Z³

to get

Y² = X³ + aXZ⁴ + bZ⁶

In this case, the point at infinity is where Z = 0, or Y² = X³, or O = (c²,c³,0). We can we can identify (c²,c³,0) with (1,1,0) giving O = (1,1,0) as a simpler way to write the point O.

Weighted projective coordinates are also commonly used with hyperelliptic curves. For a curve of genus g, (1,g+1,1)-weighted coordinates are usually used. Suppose that we have a hyperelliptic curve given by

y² = x^2g+2 + a_2g+1x^2g+1 + …+ a₁x + a₀

To embed this curve in the projective plane using (1,g+1,1)-weighted coordinates we write

x = X/Z

and

y = Y/Z^g+1

to get

Y² = X^2g+2 + a_2g+1X^2g+1Z + …+ a₁XZ^2g+1 + a₀Z^2g+2

In this case, the point at infinity is where

Y² = X^2g+2

or

Y = ±X^g+1

or the points (X,±X^g+1,0). We can identify (X,±X^g+1,0) with (1,±1,0) giving us two points at infinity: (1,1,0) and (1,-1,0). The fact that we have two points at infinity for a curve of this form instead of one probably explains why most people just think about the simpler case, hyperelliptic curves of the form

y² = x^2g+1 + a_2gx^2g + …+ a₁x + a₀

Governments do worry about costs

I recently had an interesting discussion about the huge amounts of money that governments spend on IT projects. The US government alone, for example, has spent over $1 billion on PKI and doesn't seem to have $1 billion of value to show for this investment.

In this discussion, I claimed that the government just isn't sensitive to costs. The other person, who happens to be a government employee, claimed that I was wrong. He claimed that governments are indeed sentitive to costs - they're just not sensitive to bad ideas. That's a distinction that I hadn't heard before.

The dentist's office effect

I just came across what I call the "dentist's office effect" again. This happens to me when I'm waiting in my dentist's office for my appointment and I end up surprised by the reading material. The selection often isn't the best in dentist's offices, but I often find some sort of magazine about computers to pick up and read. When they were still publishing a printed version, this was often a copy of Computer Shopper. After that publication went to a web-only format, the magazine that I pick up seems to be different every time.

In any case, when I'm looking through whatever magazine that I pick up, I'm often surprised by the advertised price for some sort of computer. No way, I think, that price is outrageous.

Then I notice that the magazine is a year or more old.

The Dark Side of Cloud Computing

I recently came across an interesting report by the Burton Group - "The Dark Side of Cloud Computing." This report talks about the usual issues that people always talk about around cloud computing (security, vendor lock-in, etc.), but it also had an interesting list of the unintended consequences of cloud computing:

• Data loss
• Predictability of volume
• Core vs. commodity business strategy
• Organization dis-integration
• Inadequate knowledge of internal costs and business capabilities
• Unexpected expenditures
• Inadequate budget forecasting
• Unnecessary risk
• Unintended changes to operational procedures

This report is probably worth tracking down just for the discussion of those unintended consequences.

Webinar - Managing Third Party Data Privacy

Our marketing guys have yet another webinar planned, this time it will be held on June 16, 2010 from 10 am Pacific/1 pm Eastern and will last for 60 minutes. The topic this time is Managing 3rd Party Data Privacy - Protecting Your Own and Your Partners Information. Like some of our previous webinars, this one's also sponsored by FS-ISAC, the Financial Services - Information Sharing and Analysis Center.

Here's what they plan to talk about:

• How to ensure the protection of partner information and confidently manage third-party access to card holder and personal data, including protecting terabytes of files on mainframe and legacy systems
• Why a comprehensive end-to-end approach to data protection is critical to ensure the privacy of personal and sensitive information
• What market-leading organizations — such as AAA — really require in an enterprise data protection solution

The fact that one of the infrastructure consultants for AAA will be talking about his experiences is probably a good enough reason to check out this webinar. Every industry has it's own interesting set of problems that it faces and it's fascinating to see how they find clever uses of IT to solve these problems. I've never dealt with an organization like AAA, so I have no idea of the particular challenges that they face, but I'm certainly looking forward to hearing about them on this webinar.

Projective coordinates for hyperelliptic curves

The simplest way to embed a hyperelliptic curve in projective space is by the change of variables

x = X/Z

y = Y/Z

This causes a problem, however, because this actually makes the point at infinity singular. Here’s why.

Suppose that we have a hyperelliptic curve given by

y² = x^d + a_d-1x^d-1 + …+ a₁x + a₀

If we make the change of variable

x = X/Z

y = Y/Z

we then get

Y²Z^d-2 = X^d + a_d-1X ^d-1Z + …+ a₁XZ^d-1 + a₀Z^d

When Z = 0, we have that X^d = 0 or X = 0, so O = (0,1,0) is the point at infinity for this curve.

Writing

f(X,Y,Z) = Y²Z^d-2 - X^d - a_d-1X ^d-1Z - …- a₁XZ^d-1 - a₀Z^d

we find that

∂f/∂X = -dX^d-1-…-a₁Z^d-1

∂f/∂Y = 2YZ^d-2

∂f/∂Z = (d-2)Y²Z^d-3- a_d-1X^d-1 - … - da₀Z^d-1

If we have d ≥ 4, which includes all hyperelliptic curves , then substituting O = (0,1,0), or X = 0, Y = 1 and Z = 0, into each of these we find that at O we have that

∂f/∂X = ∂f/∂Y = ∂f/∂Z = 0

or that the point at infinity is singular. That's not good. Instead, a better change of variable to use is

x = X/Z

y = Y/Z^g+1

where g is the genus of the curve, that doesn’t give you a singular point at infinity, so it avoids that particular problem.

Is PKI really that bad?

At the recent Key Management Summit, we scheduled a few minutes at the end of each day so that people could get up and talk about whatever issues they felt like talking about. The intent was to provide a way for people to tell the others about ideas that they had had while listening to the various speakers' presentations. I had never seen this done before, but it seemed to work fairly well.

The impromptu session at the end of the second day was particularly interesting. One of the attendees, Ben Gittins, got and asked for opinions on what he had read about PKI. Peter Gutmann, for example, is now working on a new book, and Ben had read a preliminary version of this book's chapter on PKI. Apparently Peter's new book does not describe PKI in a positive way (if you're familiar with Peter's thoughts on PKI, you'll know that that's a huge understatement), and Ben wanted to know if we really thought that PKI was as bad as Peter describes it to be.

It didn't take long for the group to reach a consensus. A few people simply said, "Yes, it really is." That's about as far as the discussion got. After that, there really wasn't much more to say.