written by jamesd@echeque.com
This code is based largely on the public domain code of George Barwood, Paulo S.L.M. Barreto and Steve Reid , as documented in each source file.
Download KongTools source code (requires Visual C++ 5.0 to compile)
Explanation of Elliptic Curve Cryptography.
The big problem in cryptography is key distribution. If Bob and Alice have to both know a secret key in order to communicate secretly, how does Alice tell Bob the key secretly?
So we need a one way operation where you can calculate the encryption key from the decryption key, but you cannot calculate the decryption key from the encryption key.
Then Alice chooses a decryption key at random from a very large set of possible keys (in the case of this particular implementation one of 2^240 possible decryption keys, that is 1 of 1700 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 possible keys) then she calculates the encryption key, and publishes it in plaintext to Bob, and anyone else, and to the whole world. So the decryption key is her secret key, which she alone knows, and which she alone can use to sign messages she sends, and decrypt messages sent to her, and the encryption key is her public key, which everyone knows.
The work factor for this implementation is believed to be the square root of the number of possible keys, not the number of possible keys. An attacker would have to try 2^120 keys (1 329 000 000 000 000 000 000 000 000 000 000 000 keys ) in order to obtain enough information to deduce the correct key. (He would also have to have very large storage)
Elliptic curves provide us with a suitable one way operation:
An elliptic curve is not actually part of an ellipse, rather it is a curve of the form y.y + x·y = x.x.x + a·x + b
For the purposes of elliptic curve cryptography x and y will not be real numbers but will be finite fields, typically integers modulo some quantity.
The important and interesting property of an elliptic curve is that given two points on an elliptic curve, there is a function that gives us a third point on the curve.
This function is associative and commutative. If P, Q, and S are points on the elliptic curve, then f(P,Q) = f(Q,P) and f(P,f(Q,S)) =f(f(P,Q),S), so it is convenient to represent this operation as addition of points on a curve, so that the preceding relations are represented in as P+Q = Q+P and P + (Q+S) = (Q+P)+S
In actual fact actually performing this operation involves multiplication and division, and nicely munges the bits, but it acts like addition.
Because it acts like addition we can define the operation of multiplying a point on an elliptic curve by an integer. For the purposes of cryptography, these will of course be very large integers.
Thus 3.P = P+P+P, and so forth for 10P, 1000P, etc.
Of course actually doing a thousand additions would be intolerably slow, but we can take advantage of associativity to calculate 2P=P+P, 4P=2P+2P, 8P=4P+4P, so we can multiply an elliptic curve point by a very large integer in a time proportional to the number of bits in the integer, which is quite fast.
So we can easily calculate Q = nP, given n and P, where n is a very large number, but it is very hard to find n, given Q and P. We can multiply, but division is very hard. This is our one way operation, which we need to solve the key distribution problem. This is also called the discrete logarithm problem, because this operation that we do on elliptic points is as much (and as little) like multiplication as it is like addition.
We choose a point G, which we will call the generator. Everyone using this cryptographic system will use the same point G. We will only employ a subset of the possible points on the elliptic curve, points of the form 1G, 2G, 3G, 4G, 5G ....
So Bob's secret key will be an integer b, and his public key will be an point on the elliptic curve B = b.G
Bob sends a signed message to various people containing his public key.
He digitally signs the message as follows.
Since we are employing finite fields to represent our elliptic curve points, there will be some large finite integer n such that (n+m).G = n.G
Thus our large integers that we will use will all be done modulo n.
We create a function that constructs an integer from a elliptic curve point, perhaps by taking the x coordinate of the point, though any method that will almost always give a different integer for a different point will work, such as taking the hash of the point.
Let int(P) denote an integer generated from an elliptic curve point.
Bob constructs a one way hash, h, of the message.
Bob chooses a true random number k, which must be a different random number for each message. If ever anyone discovers this random number, they will be able to find Bob's secret key. If Bob ever uses the same number k for a different message, and they know or suspects the two messages employ the same number k, they will be able to find Bob's secret key, so we need a good generator of true random numbers.
Bob calculates r and s.
r = int(k.G)+h
s = k - b.r
He appends r, s and B to his message (B is his public key B = b.G)
Alice, and perhaps many other people, read Bob's message.
Alice determines that the person who possess the secret key corresponding to B, h= r - int(sG + rA) sent the message by calculating h = r - int(s.G + r.B), and determining that h is indeed the hash of the message.
This magic work because:
s.G+r.B
= (k-b.r).G + r.b.G
Which thanks to commutativity and associativity
= k.G
Alice can use this to determine that other messages or certificates are signed by the same person who sent this one, and she can use the public key G to send a message in reply, a message that can only be read by the person who signed the message that she is replying to.
To send a secret message that can only be read by the author of the message to which she is replying, the person whose secret key is B, Ann chooses a random number k. She calculates k.B and uses it as a shared secret to scramble her message with a symmetric key algorithm such as Arc4. She then calculates K= k.G, and prepends K to her message.
Bob receives the message, which may have been intercepted by several people who would dearly like to know what Ann is sending to Bob. But only Bob knows his secret key B. He calculates b.K, which is of course equal to k.B by associativity, and uses it as a shared secret to unscramble the message.
In the above I gave one particular method of signing the message using elliptic curves.
There were 17000 similar methods last time anybody tried to count. Doubtless there are today many more. Of these 17000, probably a hundred or so are patented. The vast majority are unpatented.
Unfortunately no one can tell what patents claim to cover what methods. Patent claims are invariably written in windy and evasive double talk that says everything and nothing and anything.
regsvr32 KongTools.dllOpen your visual basic project. In visual basic 5.0 select Project/References/KongTools
This will add two new app global objects to your project, and three new classes.
Open Object Browser, and in Object Browser select KongToolsLib
You will see
CryptoEntropy collects entropy from mouse move events and anything else you have handy, stores it in the file Randseed.bin, and uses it to make random big integers
Crypto and CryptoEntropy are objects, not classes. You should not create them, they are already created.
EllipticInteger provides big integer arithmetic modulo the order of G, the generator.
EllipticPoint provides elliptic curve arithmetic.
Typical usage:
Dim kInt As EllipticInteger Dim KPoint As EllipticPoint Set kInt = CryptoEntropy.RandomEllipticInteger Set KPoint = kInt.timesGeneratorSee the function EllipticCurveSanityCheck() in the file module.bas in the visual basic source code for KongToolsDemo for more detailed examples on how to use these tools to perform the operations of elliptic cryptography. That file also contains examples for SHA1, and for managing entropy.
The property bin, for example Kpoint.bin provides access to a binary representation of the point, or the integer. This can be used to store the integer in an access database, or you can convert it to base 64 for inclusion in messages.
This is 256 bits, 32 bytes long for elliptic points (packed format, x coordinate and sign of the y coordinate), and usually 240 bits, 30 bytes long for elliptic integers, though sometimes one more bit will be needed, 241 bits, 31 bytes.
Although it is not well documented, DAO supports binary fields in a database, for example
Set tbl = .CreateTableDef("SigText", dbAttachExclusive)
With tbl
Set z = .CreateField("elliptic_point", dbBinary, 32)
z.Required = True
.Fields.Append z
End With
.TableDefs.Append tbl
The resulting fields are dynamic byte array objects in visual basic. Warning:
Automatic conversion between byte array and string usually works, but giving
strings to database functions when they expect byte arrays can produce
unexpected results. The seek method expects the correct type.
SHA provides, of course, the SHA hash.
Typical usage:
Dim byteHash() As Byte Dim hash As New SHA hash.process_ansii txtText.Text hash.process_ansii SomeMoreText byteHash = hash.final
!997 September 22 Version 1.0: Minor API changes. KongTools now provides visual basic style error handling when you pass one of its functions an uninitialized variable. A visual basic program to test and demonstrate the KongTools functions is now part of the release. No bugs in this version known as yet.
1997 December 3 version 2.0: Added Arc4 Symmetric key encryption. (Which has another name when you pay Ron Rivest's company.) This version is used by Crypto Kong, a digital signature and communications encryption product released at the same time. This version had a serious bug, which prevented it from running on windows 95, though it ran just fine on windows NT
1997 December 11 version 2.0: Bugfix release