Scott Vanstone | Cryptography thrown an elliptic curve

Scott Vanstone, along with two of his former students at the
University of Waterloo in Ontario, Alfred Meneze and Mingha Qu,
invented elliptic curve cryptography. As a professor of mathematics
and computer science at the University of Waterloo, Vanstone
devotes much of his research to the implementation of ECC. As
co-founder and executive vice president of strategic technology at
Certicom, he promotes the use of the company's technology in
public-key infrastructures.

He is co-author of 'A Guide to Elliptic Curve
Cryptography.'

GCN: Without getting too deeply into the math, what is
elliptic curve cryptography?

Scott Vanstone: Elliptic curve cryptography is a public-key scheme providing the same functionality as the RSA scheme. [RSA is a publickey algorithm
named after its three inventors, Ronald Rivest, Adi Shamir, and
Leonard Adleman]. The difference is that elliptic curve bases its
security on a much harder mathematical problem than the problem RSA
bases its security on. That translates into being able to use much
shorter key lengths to get the equivalent level of security. There
are really only two commercially viable public- key schemes,
elliptic curve cryptography and RSA. RSA, in my opinion, will be
replaced because of the technological advantages of ECC.

GCN: Is the level of security something that can be proved,
rather than a matter of opinion?

Vanstone: It has been around now for 23 years. It's
been looked at by the best mathematicians in the world, just as RSA
has, and nobody has found any weaknesses in it. It is a
well-established technology.

GCN: Strengths and advantages usually come with some
trade-offs or weaknesses. What are the relative strengths and
weaknesses of ECC?

Vanstone: The strength is a shorter key size. The Advanced
Encryption Standard (AES) is a symmetric key algorithm. It requires
a common key used by both parties. There are three key lengths
specified ' 128, 192 and 256 bits. In good cryptographic
practice, you always match key strengths. If I want to pass a
symmetric key using a public-key scheme, I should be using a public
key that has the same number of bits of security. To exchange a
128- bit key, if we use elliptic curve cryptography, we need to use
a 256-bit ECC key. If we wanted to use RSA to pass that 128-bit
key, we'd need more than 3,000 bits of RSA to get the
equivalent strength. If you want to exchange a 256-bit AES key, you
would need 512 bits of ECC key, and if you use RSA you would have
to use over 15,000 bits. Elliptic curve key sizes scale linearly,
where RSA goes up sub-exponentially. These numbers showing
key-strength equivalents come out of [The National Institute of
Standards and Technology]. This translates to less bandwidth use,
fewer computations and longer battery life. Disadvantages or
weaknesses? We don't know of any.

GCN: If ECC is a more efficient scheme, why has RSA been
implemented in so many PKI applications?

Vanstone: RSA was the first player in the game. RSA was
founded in 1977, and ECC was not discovered until 1985. In the
security industry, there is a huge barrier to entry. It takes an
enormous amount of time to get a foothold. ECC is now at that
stage. It is recognized as being stronger.

GCN: What applications is ECC best suited for?

Vanstone: Any application that requires confidentiality or
encryption of data, data integrity, authentication, or
nonrepudiation. Nonrepudiation with a digital signature is a
concept only public keys can deliver. You can't get digital
signatures and nonrepudiation with a symmetric key scheme.

GCN: The uses you mention are all functions of PKI, which
does not in itself use symmetrical encryption keys. Yet PKI is
typically used to exchange symmetrical keys for encryption. Why use
symmetrical key algorithms at all? Why not do all of the encryption
with public/private keys and PKI?

Vanstone: Symmetric key algorithms such as AES are blazingly
fast. If you are encrypting large messages, AES will likely run a
thousand times faster than public-key encryption. But the
difficulty with symmetric key cryptography is how we exchange the
keys. The answer is public-key cryptography. It's great for
exchanging these keys. It's a hybrid scheme with the best of
both worlds. We use public keys to pass symmetric keys for
encryption.

GCN: How is ECC being used today?

Vanstone: The [Research In Motion] BlackBerry is completely
secured by elliptic curve cryptography. They have adopted 256-bit
AES for protection and ECC at 512 bits for the key exchanges. The
new e-passport standard has elliptic curve in it. It's being
used in digital postal marks to provide digital signatures on those
2-D bar codes you see on an envelope. Another application is
consumer electronics, such as a flat-screen TV. The link between a
DVD player and the TV is a digital link, and content providers will
not give content unless that link is encrypted. In any constrained
environment, ECC is well-suited.

GCN: Does ECC have the government's blessing?

Vanstone: We were approached by the National Security Agency
in 2003, and they got a license for 26 of our technologies. Then at
the RSA Conference in 2005, they announced Suite B. This is the
first time NSA has endorsed a suite of cryptographic algorithms.
That consists of a symmetric key scheme, which is AES; a digital
signature scheme, which is ECC; a key agreement mechanism, which is
ECC; and the hash function [Secure Hash Algorithm] SHA 2. So the
U.S. government likes it.

GCN: What have been the greatest changes in cryptography in
the past 20 years?

Vanstone: I have one foot in academia and I started
Certicom. In my experience, cryptography has gone from a
nice-to-have to a must-have. So it is being built in from the very
beginning rather than bolted on. And we haven't had the
ability in the past to offer high security in very constrained
environments. Elliptic curve cryptography allows us to do that now.
We can provide the same kind of security the banking industry would
want for tiny networked devices.

GCN: What are the greatest challenges that face the
cryptographic industry now?

Vanstone: A big challenge, at least for ECC, is to replace
the legacy equipment that is out there and to put PKI in place.
That is happening.

GCN: What will the next big development in cryptography
be?

Vanstone: There won't be a more efficient scheme, in
my opinion, than ECC. Perhaps way down the road you might see
quantum cryptography. People are talking about it today, but it has
a long, long way to go.