Fifty Shades of J/Chapter 39
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
Principal Topics
- [ (left) ] (right), ~ (reflex) ciphers, public/private keys, clock multiplication, inverse, multiplicative inverse, exponential ciphers, RSA ciphers
Dear J-ohn and J-anet,
How would you like to be a security man or woman when you grow up? It’s a very important job these days on account of the enormous volumes of personal and business data which fly through cyberspace every microsecond. If this is a career which attracts you, have you considered telling your teacher what a very good medium J is for getting started in this area?
Here are a few things you should know before we find you a uniform. First you should appreciate that cryptographic systems divide broadly into two categories, namely those based on transposition and those based on substitution. (I’m afraid you will have to ask your Mummy or Daddy to explain what these big words mean). In practice many current coding systems involve both of these techniques. Your first lesson will concentrate on a subset of the second of these subdivisions, that is on those in which characters are first converted to numerals and then replaced by ciphers. The systems concerned work to a general pattern in which there are keys of two kinds, public and private. I make a public key freely available to anyone who wants to send me enciphered messages. The relative security of any cryptographic system is proportional to the time taken by the “enemy” (that is the hackers) to determine a private key which allows me, and only me, to decipher messages. I am aware of course that the enemy will analyse my messages in order to try and break the code by discovering my private key. This is the process which is known as cryptanalysis.
The basics of such methods are simple, and J is great for describing them. My first illustration concerns multiplicative codes which depend on the clock arithmetic which you do at school. As you know, the world of sums contains only positive integers and small ones at that. Should any of these accidentally get too big for their boots, they are simply trimmed down to size by taking away the clocksize. And should one of them stray into naughty negative regions then adding the clocksize (cs) an appropriate number of times is all that is needed to bring it back into the orderly region of i.cs .
The essence of clock multiplication is the remainder verb | applied to a table based on i.
cmultab=:|*/~@i. NB. clock multiplication table cmultab 5 0 0 0 0 0 0 1 2 3 4 0 2 4 1 3 0 3 1 4 2 0 4 3 2 1
(If you don’t like the column and row of zeros just drop them:
cmtab=:| */~@ }.@:i. cmtab 5 1 2 3 4 2 4 1 3 3 1 4 2 4 3 2 1
The inverse of a clock number x is that value y for which xy=1 in clock arithmetic, so that for cs=5 the tables above show that 1 and 4 are self-inverse, and that 2 and 3 are each the inverse of the other.
Now assign a different clocksize :
cs=.26
From this you can guess that I have an alphabetic message in mind, with letters translated into numbers in the obvious way, A=1, B=2, etc. Encryption consists of multiplying each message number by the public key, (that is one of the numbers between 1 and 25 which has no common factor with 26) and then simplifying this by clock arithmetic
enc=:cs&|@* NB. x=key, y=number 5 enc 22 5 3 20 15 18 NB. encrypt "VECTOR" 6 25 15 22 23 12
To decipher this coded message I need to repeat this process, only now using the inverse of 5. The restriction put on the key in parentheses above guarantees that such a number will exist and be unique. To find the multiplicative inverse of a key with respect to cs, multiply the key by all the integers in the field and perform clock arithmetic using the key. The inverse is the index of whichever of these values is one:
minv=:i.&1@(]|(*i.)) NB. syntax is 'key minv field' 5 minv 26 21
Decipherment of ‘VECTOR’ as coded above is simply a further encryption using the inverse key:
21 enc 6 25 15 22 23 12 22 5 3 20 15 18
I make 5 known to all my correspondents as a public key, and hence implicitly to the enemy, who is presumed to be smart enough to work out the broad method, but needs to know cs in order to discover the inverse key which turns code back into plain text. It would not be a very difficult exercise to find these quantities using the parameters above, however by using a much larger cs, and redefining the encrypting verb so that letters are dealt with in blocks, a modest degree of security can be achieved:
cs=.2752 enc=:cs&|@* 379 enc 2205 320 1518 NB. key=379, "VE CT OR" 1839 192 154 379 minv cs NB. multiplicative inverse of 379 1779 1779 enc 1839 192 154 NB. decipher coded message 2205 320 1518
One step which could be made towards greater security is to use an exponential cipher rather than a multiplicative one, that is instead of multiplying the code by the key, it is raised to the power of the key. Uniqueness of inverse requires that cs be a prime number. Otherwise the only change in J terms is from * to ^ in enc :
cs=.29 cs | 15 ^ 22 5 3 20 15 18 0 10 11 0 0 0
The zeros in the above indicate that there is a problem, namely that numbers such as 15^22 are very large and are approximated when represented as floating-point values. The residue of the approximate value is not useful. This is easily solved since
- exponentiation is just repeated multiplication, and
- multiplication in clock arithmetic follows the rules of multiplication in ordinary arithmetic, that is if a and b are the values of A,B and C when reduced to clock integers, then ab, if necessary reduced to a clock integer, is equal to the clock integer reduction of AB. (In mathematical terminology a=A(mod n) and b=B(mod n) implies that ab=AB(mod n) ).
So define clock multiplication:
mul=:cs&|@*
and insert this into key replicates of the code:
eenc=:mul/@# 5 eenc &> 22 5 3 20 15 18 NB. encrypt “VECTOR”, key=5 13 22 11 24 10 15
The & conjunction (&> is equivalent to every) is necessary due to the non-scalar nature of the verb mul .
For the purposes of decipherment, mathematics dictates that the inverse key is the multiplicative inverse of one less than cs:
5 minv 28 NB. multiplicative inv. of 5 17 17 eenc&> 13 22 11 24 10 15 NB. decipher message 22 5 3 20 15 18
This improves security a bit, but not by an enormous amount since an enemy with computers at his disposal would not take long to work out cs and hence, given that my key is public knowledge, to work out the inverse of cs. A cryptographer’s Holy Grail is to find a way in which to make his key completely public so that anyone can send him messages, while at the same time making the rule for computing the decipherment key so complex that the enemy has little hope of finding it, however massive the computing power he has available. This remained an open problem in the world of cryptography until 1977 when a major breakthrough was achieved through the invention by of the so-called RSA ciphers at the Massachusetts Institute of Technology. These are named after the initials of their inventors R.L. Rivest, A. Shamir and L. Adelman. Their idea was that cs should be the product of two primes, say 3551=53*67, following which any public key must then be coprime to (53-1)*(67-1)=3432, which is also the number used to calculate the multiplicative inverse. Choosing 191 as the key, and resetting the eenc verb gives:
cs=.3551 eenc=:(3551&|@*)/@# 191 eenc every 2205 320 1518 NB. encipher “VECTOR", key=191 489 2774 2274 191 minv 3432 NB. multiplicative inv. of 191 575 575 eenc every 489 2774 2274 NB. decipher message 2205 320 1518
Of course the primes used in the above illustration are very small. In practice two very large prime numbers, say of the order of 10200, would be chosen. Factoring products of this size is a very hard problem given the present state of the mathematical and computational arts, and so what is available to me is a public key which I can broadcast to everybody, but for which, provided I keep the two prime factors a secret, I have a private key which, ensures that only I can decipher my incoming messages.
Now, dear J-anet and J-ohn, just think how little programming you have had to do to take you from the clock arithmetic which you love to techniques which are the basis of the day-by-day encryption of millions of business and financial transmissions. Will it by any chance be one of you who cracks the factoring algorithm? (For the answer, see Vector volume 99 no. 4).
Code Summary
(Note : clocksize cs must be dynamically reset to an integer value).
cmultab=: |*/~@i. NB. clock multiplication table cmtab=: | */~@ }.@:i. NB. ditto dropping zeros enc=: cs&|@* NB. x=key, y=number minv=: i.&1@(]|(*i.)) NB. multiplicative inverse mul=: cs&|@* NB. clock multiplication eenc=: mul/@# NB. exponential encode