Cryptography tutorial
Here is some ultrasparc binaries.
It is also possible to compile them using the Givaro library.
The sources are in Examples/Integers.
The goal is to generate public and secret keys.
RSA principle is the following :
Take to numbers p and q, such that p.q = m is hard to factor.
Typically p and q would be big primes.
Find numbers k and u such that k.u = 1 [ (p-1)(q-1) ].
This is easily done with the Extended Euclidian Algorithm.
Then for any x, x^(k.u) = x^1 = x [ m ].
To crypt x, produce x^k = y [m].
To decrypt y, compute y^u = x [m] !
The only way to break the code is to find u.
Therefore it is necessary to know p-1 and q-1, that is to say p and q.
Breaking code is therefore to factor the public key m.
Alice and Bobby want to send crypted messages :
- Alice> echo "p q" | genkeys > Alice_keys
where p, q are the sizes of the primes used to generate the key
(ex: 120, 130 is okay on August 26th 1999).
Alice_keys contains three numbers : mA, kA, uA.
mA, kA are the public keys. uA is the secret one.
- Bobby> echo "n m" | genkeys > Bobby_keys
Bobby_keys contains mB, kB, uB.
- Alice> echo "Alice." > Alice_signature
- Alice> cat Alice_signature | code mA uA > Alice_crypted_signature
Alice (knowing uA) is the only person capable of generating
Alice_crypted_signature.
Therefore Bobby will be able to decrypt it using
Alice's public keys.
- Alice> cat Message Alice_crypted_signature | code mB kB > Crypted_message
- Alice> gzip Crypted_message
- Alice> send Bobby < Crypted_message.gz
- Bobby> receive Crypted_message.gz
- Bobby> gunzip Crypted_message.gz
- Bobby> cat Crypted_message | decode mB uB > Message
Bobby, using his secret key, is the only one able to decode a message that has been coded with his public keys.
- Bobby> tail -1 Message | decode mA kA
Alice was the only person able to create a message that her public
keys would decode. Therefore Alice is the person who sent the message.
My personal public keys are :
m: 337144557580742925403203574159835714714287842958843472211937239583183403854258960138329664087712808965050984182732565081619850749775423980303645496866770388411831192187835534750900582581234316529099609979915892660243748291796493893595813436239583125412503652317941420441840330616752073815367920563432378386429193
k: 130223017593249372556473324987764970872965264633160030348164273896325046044884178725080106703384304739989466743580985650550186229411950788826838743539647268361471981144743047692495440120012398585553389553614725835489890255654717788990780058407492316883820962732998374295090140753968664689430472298870739548067551
Last update : Aug 26 1999