Image for post
Image for post

It’s well known that the ECDSA signature (as used in Bitcoin) needs to be carefully created, or the private key can be discovered. The nightmare would thus be to sign a few messages and for Eve to then discover the private key from these. In this case, we will look at the case where Alice has two key pairs and signs four messages with these, and for Eve to discover where private keys.

Alice will have two key pairs [1], and with two private keys (x_1 and x_2). She will sign message 1 (m_1) with the first private key (x_1), sign message 2 (m_2) with a second private key (x_2), sign message 3 (m_3) with the first private key (x_1) and sign message 4 (m_4) with the second private key (x_2) The same nonce (k_1 is used for messages 1 and 2, and another nonce (k_2) is used to sign messages 3 and 4. Now let’s say we have four messages (m_1 ..


Image for post
Image for post

It is a well-known secret that ECDSA needs to be set up properly, else the private key could be revealed. In the worse case, Eve could reveal Alice’s Bitcoin private key from the ECDSA signatures. One of the weaknesses is where the same nonce value is used for different messages. So let’s crack.

With an ECDSA signature, we sign a message with a private key (priv) and prove the signature with the public key (pub). A random value (a nonce) is then used to randomize the signature. Each time we sign, we create a random nonce value and it will produce a different (but verifiable) signature. The private key, though, can be discovered if Alice signs two different messages with the same nonce. …


Image for post
Image for post

I am so pleased to see that Jacob Ziv has received the IEEE Medal of Honor. Along with Abraham Lempel he created two lossless compression methods (LZ-77 and LZ-78) and which are the basis of a wide range of compressed file types including ZIP and GIF/PNG files. In many previous compression methods, there was some loss of bits when decompressing, but Lempel and Ziv found a way to compress data so that commonly occurring bit sequences could be represented by fewer bits than less common ones. …


Image for post
Image for post

You name it, and the Internet is centre stage in the debate around recreating our societies: the rights of privacy against the rights of society to protect itself; the rights of countries to define legal frameworks and control their citizens; the rights of law to define criminal activity; and the rights of individuals to have free speech. Basically, it’s old power structures versus new ones, and the next few years will see a massive struggle between the two.

Internet boot-up

I have grown up with the Internet. For me, it has evolved from screaming modems with AOL/Compuserve dial-up connections to finally take its place in rebuilding our society in a digital way. We have thus had a few decades of it finding its way and for us to fix its fundamental technical flaws. So from RFC (Request For Comment) documents, it is now all grown-up. In computer terms, we could define the time up to now as the boot-up phase. Now that it has booted up, we enter the real phase: the governance and control phase, and where the Internet moves from being a technical infrastructure for routing data packets to actually challenging every existing authority for true power. It has mainly defeated the power print and advertising industries and is now gunning for the legal industry and our existing governance structures. …


Image for post
Image for post

We have several problems on the Internet. The first is that we have our identities harvested by companies such as Facebook and Google, and the second is that we must now prove things — such as our age or our location — and in doing so, we are revealing our information to others. So how can we create a trusted digital world, where we prove things, without revealing our sensitive information?

We have barely got to the point where we can digitally sign our documents, and where many industries still rely on wet signatures. With this, we create a public key (pk) and a private key (sk) and then use our private key to sign something. This then creates a signature (S). Our public key then validates the entity which signed it. But whenever we sign a document, it often reveals our identity, and, possibly other parts of our identity (such as our age, address, and so on). In many cases, though, such as being served in a bar, Peggy should just have to prove that she is over 18 years old, and not have to reveal her name, date of birth and address. …


Image for post
Image for post
Koblitz (left) and Miller (right)

Your online security depends fundamentally on a beautiful little curve: an elliptic curve. It has been a savour of Cybersecurity in the face of ever-increasing key sizes for RSA, and weaknesses in discrete logarithms (as used in the Diffie-Hellman key exchange method). With RSA, we are moving to 2,048-bit key sizes, but with elliptic curve methods, our private key sizes are often just 256 bits long. For example, if you have Bitcoins, your private key which enables your owner of the cryptocurrency is just 256 bits long.

So I am so pleased, today, that Neal I. Koblitz and Victor Miller have been recognized for their work with the Levchin Prize at the real-world cryptography…


Image for post
Image for post

Why we don’t give every child at school a Raspberry Pi (RPI) is beyond me. It would allow every child to see the power of software and learn operating systems, Python programming and electronics. As Computer Science at school slips every year, we may be losing another generation of technologists. In Scotland, for example, Computer Science is not even in the Top 15 subjects at school.

To me, the RPI is the answer to making software engaging for every child, and opens up learning in an almost infinite number of possibilities. From the days of the classic BBC Micro, I’ve always been a fan of standardising the platform for learning coding, and in creating shared resources. …


Image for post
Image for post
Évariste Galois — Aged 15 https://en.wikipedia.org/wiki/%C3%89variste_Galois

In 1831, Évariste Galois died of duelling wounds at the age of 20 but left a great legacy. While he was a teenager he worked on polynomials and laid down the principles of Galois theory, along with defining the concept of a finite field. In cryptography, the finite field is one of the major concepts and involves limiting the number of possible values to a limiting factor (p). The values of the field then range from 0 to p-1.

A Galois field

Within a field, we can operate on values in the field using arithmetic operations. We can thus have an infinite field, and where we could include all of the possible integers. A finite field or Galois field of GF(2^n) has 2^n elements. If n is four, we have 16 output values. …


Image for post
Image for post

Discrete logarithm methods -such as with Diffie-Hellman — are not efficient these days as the prime number often has 2,048 bits or more. We thus focus more on elliptic curve methods, and which are much faster. The basics of them is to convert g^x (mod p) into xG, and where G is the base point on a curve, and x is the scalar. We thus perform a point multiplication rather than an exponential. When it comes to a multiplication, such as g^x g^y (and which is equal to g^{x+y}), we perform a point addition, such as xG + yG (and which is equal to (x+y)G). And that’s it, just two core operations: a point multiplication, and a point addition. So let’s convert a method which was defined in discrete logs as an elliptic curve method. …

About

Prof Bill Buchanan OBE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store