Elliptic curve integrated encryption scheme
Elliptic curve integrated encryption scheme
As it is common in cryptography - related narratives, imagine we have two communicating parties - Alice and Bob (because plain A and B is boring). Let’s now say Alice has a 3D model of main gates of a fortress she needs to secretly share with Bob (maybe they are planning to hunt for a treasure...), but they do not have a secure communication channel set up. She can’t openly send it to him - other treasure hunters are only waiting for her to do so and get to the treasure first. Nor can she send Bob an encryption key for the same reason - enemies will be able to intercept their communication at any time...
In[]:=
model=ExampleData[{"Geometry3D","CastleWall"}]
Out[]=
Alice knows there exists public-key cryptography, which seems to solve the issue. Bob generates a pair of public and private keys, shares his public key and hides his private key somewhere safe. Now Alice can send him messages encrypted with the public key and rest assured that only Bob himself will be able to decrypt them with his private key.
In[]:=
BobKeys=GenerateAsymmetricKeyPair[]
Out[]=
PrivateKeyPrivateKey,PublicKeyPublicKey
However, there is an issue with public-key encryption: it can only encrypt data smaller then the key size. For RSA it is usually 256 b - 1Mb in practice.
In[]:=
Encrypt[BobKeys["PublicKey"],model]
Out[]=
$Failed
and the model is quite large...
In[]:=
ByteCount[model]
Out[]=
990024
A possible solution to this is an elegant idea - two parties can generate a secret key, to use it with symmetric block ciphers able to encrypt data of any size and fast, but instead of sharing it openly for anyone to intercept they first encrypt the future quite short key itself using public-key encryption. A similar idea, for example, lies in the heart of a TLS handshake used by browsers and applications to communicate with servers. Elliptic curve integrated encryption scheme is a hybrid encryption scheme based on the same idea of combining asymmetric elliptic curve security with symmetric encryption. I will use here the both documented and not-yet documented functions in Wolfram Language, but all of them are accessible to the users.
In[]:=
Needs["Cryptography`"]
Alice :
Alice :
◼
To setup communication in this scheme Alice first needs to generate an elliptic curve pair of public and private key, and share with Bob her public key:
In[]:=
keysAlice=GenerateAsymmetricKeyPair["EllipticCurve"]
Out[]=
PrivateKeyPrivateKey,PublicKeyPublicKey
In[]:=
publicAlice=keysAlice["PublicKey"]
Out[]=
PublicKey
Bob:
Bob:
◼
After receiving Alice’s public key Bob proceeds to create a common secret key they will use for future efficient communication using symmetric encryption. First, he generates a random number:
In[]:=
r=RandomInteger[2^128]
Out[]=
258463691413340474926672745301378497817
◼
Next, this random number is multiplied by generator point of the elliptic curve to obtain a new point R on the curve:
G=$EllipticCurvesParameters["secp256k1"]["G"];
In[]:=
p=$EllipticCurvesParameters["secp256k1"]["p"];
In[]:=
R=MultiplyEllipticCurvePoints[r,G,p]
Out[]=
{56388661215435006594672350584082368211644784172476208670077630186492252291867,93683196637230916332457578422263289268422620818264252434375401493567201506296}
◼
This point R he will send to Alice and she will derive their common secret key from it.
◼
Same random number Bob also multiplies by Alice’s public key elliptic curve point:
BobS=MultiplyEllipticCurvePoints[r,publicAlice["PublicCurvePoint"],p]
Out[]=
{11928314003818744887780451493011702155750344705473403150336990415492893790368,114509385742476457423421051014701119983282082067769968077883273587461958496608}
◼
The secret symmetric key for communication between Alice and Bob is going to be the x-coordinate bytes of the obtained point
In[]:=
BobSecretBA=ByteArray[IntegerDigits[BobS[[1]],256,32]];
◼
Let’s turn the bytes into a key that can be used for AES block cipher:
BobSecretKey=GenerateSymmetricKey[BobSecretBA]
Out[]=
SymmetricKey
◼
Check that it actually works:
In[]:=
Encrypt[BobSecretKey,"Hello"]
Out[]=
EncryptedObject
In[]:=
Decrypt[BobSecretKey,%]
Out[]=
Hello
Alice :
Alice :
◼
Alice receives the point R on the curve from Bob:
In[]:=
R
Out[]=
{103913431517270206531560860360977174803978011517328255959529289433535399347332,103892754434933944566667044309256005800354789745203278858047863408321455928384}
◼
She then multiplies it by a her private key:
AliceS=MultiplyEllipticCurvePoints[keysAlice["PrivateKey"]["PrivateMultiplier"],R,p]
Out[]=
{11928314003818744887780451493011702155750344705473403150336990415492893790368,114509385742476457423421051014701119983282082067769968077883273587461958496608}
◼
Same as Bob did, Alice takes bytes of the x-coordinate of the point S she just computed:
In[]:=
AliceSecretBA=ByteArray[IntegerDigits[AliceS[[1]],256,32]];
◼
And turns the bytes into a key that can be used for AES block cipher:
AliceSecretKey=GenerateSymmetricKey[AliceSecretBA]
Out[]=
SymmetricKey
◼
Check that it actually works:
In[]:=
Encrypt[AliceSecretKey,"Hello"]
Out[]=
EncryptedObject
In[]:=
Decrypt[AliceSecretKey,%]
Out[]=
Hello
Result
Result
We can see that Bob and Alice have in fact computed the same secret key without having to ever share or expose it to unprotected channels of communication. Alice never saw or received the value of S computed by Bob from her public key - she obtains the same value independently based on knowing her own private key.
In[]:=
BobSAliceS
Out[]=
True
In[]:=
AliceSecretKeyBobSecretKey
Out[]=
True
Now Alice can send Bob data of any size encrypted with this secret key of hers and Bob will be able to decrypt it with his and vice versa.
Encrypt[AliceSecretKey,model]
Out[]=
EncryptedObject
In[]:=
Decrypt[BobSecretKey,%]
Out[]=