How to Ride a “BiCypher”

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 85

Bicycle, bi’si-kl, n, A two-wheeled vehicle propelled by the rider.
(The Graduate English Dictionary.)

Bicypher, bi’si’fer, n, A two-keyed form of secret writing.
(The Cannon Warped Mind.)

Working examples of Public Key Cryptography with Small Integers¶

I have been fascinated by the concept of Public Key Cryptography, that is where a message encoded with a public key can only be decoded with the corresponding private key. Additionally to hiding the contents of a message, the system can be used in reverse to authenticate who the sender is. By the sender encoding a "signature" with their private key, only their public key decodes it, proving it came from them.

I will try to explain the process with 3 simple APL functions and examples using small integers, leaving it up to you to try them with the code John Sullivan provided in his excellent articles on "Multiprecision Arithmetic" [1], that is, if you have the time and a very fast computer. For a more detailed and accurate description see "New Applications of Mathematics" [2], which was my source and inspiration. I have simplified the process somewhat, as I have never fully mastered modulo arithmetic, and still don’t know the difference between encoding, enciphering, encyphering and encrypting.

The Functions¶

I have one function to encode a text string "enc", and a second to decode the result "dec". These handle text-to-numeric and numeric-to-text conversions. Both functions use a utility that I call "modpower" which does the real work.

There is also a set of 3 globals: "private" (the private key), "public" (the public key) and "mod" (the base of the modulus arithmetic).

The Explanation¶

The whole process relies heavily on some aspects of modular arithmetic, which I won’t go into (mainly because I don’t understand it). See [2] above.

Try the expressions below with the set mod=17, public=5 and private=13; or an alternative set mod=143, public=73 and private=97.

The key to the way it works is that for certain sets of values of "public", "private" and "mod":

      (⍳10) ≡ (public×private) modpower ⍳10            (Expression 1)
1

Using both the public and private keys, the expression has no visible effect on the message. But if we just use the "public" key we can encipher the message thus:

      public modpower ⍳10                              (Expression 2)
0 1 46 113 114 60 50 106 96 42

(Note that the actual values returned will depend on the values of "mod" and "private".)

Following on, to decipher the message we repeat the process on the last result but this time using the "private" key

      private modpower 0 1 46 113 114 60 50 106 96 42
0 1 2 3 4 5 6 7 8 9                                    (Expression 3)

I like to think of this process as a cog wheel, with a ratchet on it so that it only turns in one direction. Each movement of the wheel jumbles up the message (like rotating a face on a Rubic cube) but each "complete rotation" brings it back to the original message (see expression 1 above). The public key turns it through x degrees, where x is less than 360 (see expression 2 above), the private key through 360-x degrees (see expression 3 above). The public and private keys complement one another and are equivalent to an integer number of rotations.

Note that after expression 2 you can’t turn it back through -x degrees because of the ratchet effect built into modpower. The ratchet effect is partially produced by the effects of modulus arithmetic, which because it loses information, is irreversible. The reverse process produces multiple possible solutions of which only one is correct.

Connecting Public and Private¶

Without going into the maths of it, when "mod" is prime, the "public" and "private" keys are connected by:

      1=(mod-1)|public × private                        (Expression 4)

or if "mod" is the product of 2 prime numbers p and q:

      1=((p-1)×q-1)|public × private                    (Expression 5)

Try expression 4 with: public←5 ⋄ private←13 ⋄ mod←17 and expression 5 with: p←11 ⋄ q←13 ⋄ tm←(p-1)×q-1 ⋄ public←73 ⋄ private←97 ⋄ mod←p×q

Creating the Keys¶

Fixing the values used for "private" "public" and "mod" is actually far harder that the actual encryption/decryption. I will go through the steps I used to create a public/private key set for the simple example above:

1. Choose two prime numbers p and q, e.g. 11 and 13.
   In real life, to make the code extremely difficult to crack, they would be very large numbers with say 256 bits.
2. Multiply p and q to produce the value to use as "mod", e.g. 143 (11 × 13).
   Note that "mod" would be a 516-bit number with only 2 factors p and q.
3. Calculate the product of (p-1) and (q-1) (call it tm), e.g. 120 (10 × 12)
4. Choose a prime number less than "mod" as our "public" key, e.g. 73.

5. Calculate a corresponding "private" key which satisfies the equation

   1= tm | public × private
   

e.g. 97 (120|73 × 97) is 1

The 3 functions along with the public key and mod can be published. The private key should be kept secret, as should the values of p, q and tm may be destroyed.

If you are a cipher breaker, and you have been given "mod" and "public", to derive "private" you need to know "tm" which is itself derived from the factors of "mod" (p and q). However, it is VERY difficult (i.e. a long slow process) to calculate the factors of a very large number. Remember we created "mod" as a 512-bit product of two primes.

As to deciphering the encoded message by using the public key and reverse engineering the algorithm used by modpower, think of trying to do the inverse of times reduction on a scalar to produce a vector. The inverse process produces many possible solutions of which only one is the correct answer.

Function Listings¶

 r←enc text;⎕IO
⍝Converts <text> string as encyphered numeric vector
 ⎕IO←0
 r←public modpower(,⍉16 16⊤⎕AV⍳text)
 r←dec num;⎕IO
⍝Converts numeric vector to deciphered text
 ⎕IO←0
 r←(⎕AV)[16⊥⍉(((⍴num)÷2),2)⍴private modpower num]
 r←k modpower c;s
⍝Returns mod|c*k
⍝without domain errors if k is large
 s←'mod|',(⍕c),'×'
 r←⍎(((⍴s)×k-1)⍴s),⍕c

Notes on the Function "modpower"¶

I originally wrote "modpower" as 2 operators in Dyalog APL, but have re-written it in a more simplistic style so it can be run under any APL. The original operators are "modtimes" and "code":

 r←la(m modtimes)ra
⍝Operator to perform m|la×ra
⍝operator can be used with reduction (m modtimes)/vector
 r←m|la×ra
 r←key(mod code)data
⍝Operator to Ecipher <data> with <key> using <mod>
 r←(mod modtimes)/(|(⍴data),key)⍴key/data

"modtimes" produces the same result as

m|×/la,ra

but with the added bonus that if la,ra is replaced by a longer vector, (say 500 reshape of 2000) it will still work without getting a domain error that raising 2000 to the 500 power would give. Example using "m" of 143 "private" of 97 and "public" of 73.

      73 (143 code) ⍳20
1 41 16 108 70 84 46 138 113 10 11 12 52 27 119 81 95 57 6 124
      97 (143 code) 73 (143 code) ⍳20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

References¶

[1] Multiprecision Arithmetic, John Sullivan, Vector vol. 12 nos. 1, 2, 3 & 4

[2] New Applications of Mathematics, Ed by Christine Bondi, Penguin Books, 1991