Introducing RPicSim

Check out the post I recently wrote on the Pololu blog: Introducing RPicSim. It talks about a tool we made for using Ruby, RSpec, and test-driven development to aid the development of PIC microcontroller firmware.

Version 2.0.0 of minimu9-ahrs released

This week I released version 2.0.0 of minimu9-ahrs, which adds support for the MinIMU-9 v3. You can see more information on the Pololu blog.

Introducing the Ruby ECDSA gem

I am happy to announce that I released version 1.0.0 of the Ruby ecdsa gem today. ECDSA stands for Elliptic Curve Digital Signature Algorithm. This algorithm, defined in a document called SEC1, allows you to make secure, cryptographic digital signatures of messages. The ecdsa gem is an implementation of ECDSA written almost entirely in pure Ruby.

To install the gem, run:

gem install ecdsa

One of the main purposes of the ecdsa gem is education; it is a good resource for people who want to learn about ECDSA. The ecdsa gem seems to be a lot slower than OpenSSL, but that is okay. Verifying a single secp256k1 signature with the gem takes about 280 ms on my machine.

The main reason that I made the ecdsa gem is because I wanted to do some experiments related to Bitcoin. My language of choice for experimentation is Ruby. Ruby has built-in support for ECDSA through its OpenSSL binding, but I found it frustrating to use.

Comparison to OpenSSL

Ruby's built-in OpenSSL ECDSA support is frustrating mainly because the documentation is very sparse. For example, it says on this page that you can create a new OpenSSL::PKey::EC::Point object from a "group" and a "bn". The group part is easy to figure out, but the "bn" part is not obvious at all. The "bn" stands for "big number". In general, a point can be created from a private key, which is a big number, so I would think that the "bn" argument might be the private key. Instead, the "bn" turns out to actually be a binary representation of the two coordinates of the public key, as defined in section 2.3.4 of SEC1. There was no way to figure this out from the Ruby documentation or the OpenSSL documentation; I had to do an experiment to verify it after someone on StackOverflow explained it to me.

In contrast, the Ruby ecdsa gem documentation explains the types of all its parameters and cites official documents when appropriate. Also, the classes and routines for doing cryptography are very clearly separated from the routines for encoding and decoding data from strings. All the binary formatting routines live in the ECDSA::Format module, and the parts of the gem that do actual cryptographic calculations do not depend on them.

Here is a bit of Ruby code showing how you would verify an ECDSA signature using OpenSSL and then again using the ECDSA gem:

digest =
  "\xbf\x91\xfb\x0b\x4f\x63\x33\x77\x4a\x02\x2b\xd3\x07\x8e\xd6\xcc" \
  "\xd1\x76\xee\x31\xed\x4f\xb3\xf9\xaf\xce\xb7\x2a\x37\xe7\x87\x86"

signature_der_string =
  "\x30\x45" \
  "\x02\x21\x00" \
  "\x83\x89\xdf\x45\xf0\x70\x3f\x39\xec\x8c\x1c\xc4\x2c\x13\x81\x0f" \
  "\xfc\xae\x14\x99\x5b\xb6\x48\x34\x02\x19\xe3\x53\xb6\x3b\x53\xeb" \
  "\x02\x20" \
  "\x09\xec\x65\xe1\xc1\xaa\xee\xc1\xfd\x33\x4c\x6b\x68\x4b\xde\x2b" \
  "\x3f\x57\x30\x60\xd5\xb7\x0c\x3a\x46\x72\x33\x26\xe4\xe8\xa4\xf1"

public_key_octet_string =
  "\x04" \
  "\xfc\x97\x02\x84\x78\x40\xaa\xf1\x95\xde\x84\x42\xeb\xec\xed\xf5" \
  "\xb0\x95\xcd\xbb\x9b\xc7\x16\xbd\xa9\x11\x09\x71\xb2\x8a\x49\xe0" \
  "\xea\xd8\x56\x4f\xf0\xdb\x22\x20\x9e\x03\x74\x78\x2c\x09\x3b\xb8" \
  "\x99\x69\x2d\x52\x4e\x9d\x6a\x69\x56\xe7\xc5\xec\xbc\xd6\x82\x84"

# Verifying with openssl.
require 'openssl'
ec = OpenSSL::PKey::EC.new('secp256k1')
key_bn = OpenSSL::BN.new(public_key_octet_string, 2)  # 2 means binary
ec.public_key = OpenSSL::PKey::EC::Point.new(ec.group, key_bn)
result = ec.dsa_verify_asn1(digest, signature_der_string)
puts result  # => true

# Verifying with the new ecdsa gem, version 1.0.0.
require 'ecdsa'
group = ECDSA::Group::Secp256k1
point = ECDSA::Format::PointOctetString.decode(public_key_octet_string, group)
signature = ECDSA::Format::SignatureDerString.decode(signature_der_string)
result = ECDSA.valid_signature?(point, digest, signature)
puts result  # => true

As you can see above, OpenSSL requires you to make this weird OpenSSL::PKey::EC object which represents an elliptic curve but it also holds a reference to a public key, which is a point on the curve. The object is weird because you cannot say concisely what it really is using the vocabulary of the problem domain, which is ECDSA. In contrast, the ecdsa gem uses the ECDSA::Group class to represent elliptic curves and the ECDSA::Point class to represent points on those curves.

You will also see that OpenSSL's verification method takes an ASN1 string directly, instead of taking a more abstract object that represents a signature. As a result, it is not easy for the user to inspect the internal structure of that signature, which actually consists of two big numbers. In contrast, the ecdsa gem takes a ECDSA::Signature object, so you are not forced to use any particular binary format to represent the signature and it is easier to see what is going on.

What Ruby does at parse time

Yesterday at the Las Vegas Ruby Group, someone was surprised that Kernel#global_variables will list global variables that have not been used yet. The same thing is actually true for symbols and methods, as shown here:

p Symbol.all_symbols.map(&:to_s).grep(/neve/)
    # => ["never", "never_runs", "$never_global", "never_sym"]

p global_variables.grep(/neve/)  # => ["$never_global"]

def never_runs
  $never_global
  :never_sym
end

The first line of this program tells us that Ruby has already found four things. It found a symbol :never which apparently comes from the Ruby interpreter since we never defined it. It has found the name of the method in our program even though we haven't defined that method yet. It found a symbol we used in that method even though we are never going to call the method. Similarly, it found a the name of a global variable we were never going to use.

The second line just reproduces the original thing that happened at the Ruby group, and shows that Ruby is aware of "$never_global" as an actual global variable and not just a symbol.

To understand this, you need to know that Ruby does not simply run a source file one line at a time:

• First, Ruby parses the syntax of all the code in the file.

• Later, Ruby runs the code in the file.

We already intuitively know this because whenever we make a syntax error in a file, we can see that Ruby just reports a syntax error and does not run any of the other code in the file. This means it is parsing the entire file before running any of it.

So it shouldn't be surprising that the Ruby interpreter is aware of symbols and global variables before they are used; it just tells us that those things are probably recorded at parse time instead of run time. Some more evidence for this conclusion can be found in the fact that the Ruby interpreter has lots of symbol table code in parse.y.

Most of the time you can just pretend that Ruby processes your file one line at a time, but this is a case where the details of its behavior reveal a little bit about how it actually works.

The code in this blog post was executed with Ruby 2.0.0. Ruby 1.8.7 had the same results except the symbol "never" was not present.