In this paper, a generalised formulation in sequence algebraic format is proposed
which encompasses one-time pad, symmetrical and public-key algorithms. Thus
the classifications of keyed cryptographic algorithms can be unified under a
single algebraic structure. This procedure gives some insight on the relations
amongst these algorithms.
1. Introduction
A cryptosystem is an algroithm, plus all possible plaintexts, ciphertexts, and keys [1].
There are two general types of key-based algorithms: symmetric and public-
key which are briefly described as follows:
(i) Symmetric algorithms: The encryption key can be calculated from the decryption
key and vice versa. In this paper we assume that in symmetric algorithms, the encryption
key and the decryption key either remain the same or are simply related. In the latter
case, it seems that there is some overlaps with public-key systems but that is not
so because in symmetric algorithms no keys are made public. A sender
and a receiver has to agree on a key before
they can communictae securely. As long as the communcations needs to remain
secret, the key must remain secret. The symmetric alogorithm are denoted by:
Ek1(M)=C
Symmetric algorithms are further divided into stream algorithms and block algorithms
depending whether one is operating on the plaintext a single bit or byte at a
time, or a typical block of 64 bits at a time [1]. A stream algorithm operates on
a stream of characters.
Dk2(C)=M
k1 = k2 or k2 = F(k1) ..........................................(1).
(ii) Public-key algorithms (or asymmetric algorithms): The key used for
encryption
is different from the key used for decyption. The encryption key can be made
public but the decryption key cannot be calculated from the encryption key in
any reasonable amount of time. The encryption key is often called the public
key and the decrytioin key is often called the private key.
Ek1(M)=C
The concept of public-key cryptography was invented by Whitfield Diffie and Martin
Hellman, and independently by Ralph Merkle [1]. The notion was that keys could
come in pairs - an encryption key and a decryption key. Since 1976,
numerous public-key cryptography algorihtms have been proposed. Many
of these are insecure. Some are impractical because either they have too
large a key or the ciphertext is much larger than the plaintext.
Only three algroithms work well for both encryption and digital signatures: RSA,
ElGamal, and Rabin. All of these algorithms are usually too slow to support bulk
data encrytion. Therefore for bulk data, it is not feasible to use public key
systems [1].
Dk2(C)=M
k2 = F(k1) ..........................................................(2).
All cryptosystems are breakable in a ciphertext-only attack. The
only one which is unbreakable even with infinite resources is a one-time pad.
So one-time pad would be the most ideal cryptosystem but because it is
not a public key system, it has its disadvantages as it must be restricted
between a sender/receiver pair. If the pair is broken due to one finding a
new job elsewhere, then the secrecy is lost and a new one-time pad has to
be devised. Under the general
formulation proposed in this paper, a one-time pad can be viewed either as a
singular case of a public key algorithms or a member of symmetric
algorithms. However the general formulation allow further complexities to
be introduced into the one-time pad algorithms which allow the proliferations
of variations with increased security but this is not described in detail in this
paper.
2. General Formulation
We first derive a general modulus function which includes a mixed mode function or
MMF as shown in equation (3).
mod(f1(i)^f2(i),f3(i)*(number_property(f3(i))-false)/(true-false) + 1);
Note that the MMF function can generate only either numeric 1 or numeric 0 and
operates as a toggle switch but we add a value of 1 to prevent the divisor from
becoming zero. On the other hand, if f3(i) = 0, then the divisor = 1. Although possible,
f3(i) is normally chosen as a fixed value and seldom used as a stream function.
The above is propsed as a general formulation because one could introduce various
modifications to obtain one-time pad, symmetric and asymmetric algorithms as follows:
................................f3(i)*(number_property(f2(i)) - false) + 1
= modp(f1(i)^f2(i), ---------------------------------------........)
.........................................................true - false
= modp( f1(i)^f2(i),f3(i)*MMF + 1 )....................................(3).
(i) One-time pad
If the number_property predicate is a primality test such as isprime in Maple V R 3 or
primep in
Macsyma 2.2.1, and the value of f(i) is made almost infinitely large (it is impossible to find an infintely
large prime), then the modulus divisor parts can be dropped so that
equation (3) can be simplified to equation (4):
We take equation (4) as the general formulation of a one-time pad in message stream format
as m(i) and the coded stream c(i) as given by equation (5):
.......f2(i)
f1(i)...................................................(4).
Note that m(i) and e(i) are array elements which can be used to represent stream
messages either in bits, bytes, or blocks. In one-time pad, the encryption keys
are also streamed. Equation (5) is therefore an appropriate description of a one-time
pad. It is up to cryptographers on how to use these stream functions. Since a true
one-time
pad is never reused, increasing the complexity between e(i) and d(i) does not
appear necessary. However, there is some merit in a resusable one-time pad
in which case the relation between e(i) and d(i) must be made difficult to crack
just like in symmetric and asymmetric algorithms.
m(i)=f1(i)
e(i)=f2(i)
c(i)=m(i)^e(i)
and
m(i)= c(i)^d(i) = c(i)^(1/e(i))..................................(5).
(ii) Public-key algorithms
This name covers a variety of algorithms so that one could only cite specifics.
We can cite a popular example of a public key algorithm such as the RSA [3]. Since
n = p*q in RSA starts with two large primes, we need to introduce one more MMF
into equation (3). We just refer to the two MMFs as MMF1 and MMF2 as shown in
equation (6).
By choosing large but fixed primes and allow MMF(p) and MMF(q) to toggle on only
those values of p and q which are primes, we get the product
n = p*q used in RSA. Unlike in one-time pad, the encryption key e is fixed and can be
any number
that is relatively prime to (p-1)*(q-1). The fixed decryption key d is derived from the values
of p, q, and e according to equation (7).
................f2(i)
modp(f1(i),............p*q*MMF(p)*MMF(q))....................................(6).
By equating f2(i) to e and f1(i) to m, the general formulation can be reduced to the
RSA algorithm as shown in equations (8a, b).
d = modp( 1/e, (p-1)*(q-1)) ..............................................(7).
Note that unlike in the one-time pad, the encryption and decryption keys are fixed
and that n must be finite. In fact if n is made large, the system will be very slow
due to the fact the ciphertexts can be much longer than plaintexts. It is much
more difficult to design an optimal public-key system than a symmetric key
system.
c(i) = modp( m(i)^e, n ) .................................................(8a)
and
m(i) = modp( c(i)^d, n) ..................................................(8b).
(iii) Symmetric Algorithms
Symmetric algorithms are also called conventional algorithms where the
encryption key can be easily calculated from the decryption key and vice versa.
When texts refer to the keys as being the same, this does not look possible as one
must be the reverse operation of the other. For example if e is the encryption
key in exponentiation operation, then d = 1/e, i.e. derivable from e but it is
not exactly the same as e. It is doubtful whether there is a symmetrical
algorithm in which e = d unless this happens to be the value unity. The difference
between it and public key algorithm is that there is no public key to be publicised.
Therefore the algebraic construct of symmetric key algorithm is very similar to
a one-time pad with the exception that the e and d are fixed. The algorithm
therefore takes the form of equations (9a,b). m(i) and c(i) are still either stream
functions of block functions.
3. A Simple Worked Example
c(i) = m(i)^e .................................................(8a)
and
m(i) = c(i)^d ..................................................(8b).
Here we demonstrate how to test a simple one-time pad using Macsyma 2.2.1 [3]. In
view of the functionalities provided by symbolic packages, these are very suitable
for the developments of crytographic systems although in actual implementations
one would use a compiled language. It is too complicated to demonstrate more
complicated cases but these are within the reach of most competent programmers
using symbolic softwares.
Let x1 represents an arbitrary ascii string message as shown equation(9).
x1:"abcdefghijklmnopqrstuvwxyz1234567890";
abcdefghijklmnopqrstuvwxyz1234567890 ......................................................................(9).
Equation (10) is the program line used to convert characters in x1 into decimal ascii
codes but the result of this intermediate stage is not shown separately.
x2:sum((getcharn(getchar(x1,i),1))/z^i,i,1,string_length(x1));.................................(10).
For encryption, we introduce an additional funciton into equation (10) as shown in
equation (11):
c1:sum((getcharn(getchar(x1,i),1))^mod(g1(i),g2(i))/z^i,i,1,string_length(x1)); ........(11).
To decrypt ciphertext c1 we use the decryption line in equation (12).
d1:sum((getcharn(getchar(c1,i),1))^(1/mod(g1(i),g2(i)))/z^i,i,1,string_length(x1)); ....(12).
Example 1: Symbolic computations of one-time pad
Let x1 represents an arbitrary string message as shown string (13).
x1:"abcdefghijklmnopqrstuvwxyz1234567890";
abcdefghijklmnopqrstuvwxyz1234567890 ................................................(13).
We convert this string x1 using the program line given by equation (14) into decimal
ASCII codes.
x2:sum((getcharn(getchar(x1,i),1))/z^i,i,1,string_length(x1));..........(14).
Note that the function getcharn will convert string characters decimal ASCII code.
There are altogether 256 such codes ranging from 0 to 255.
97....98....99...100..101...102...103...104...105....106......107
--- + -- + -- + --- + --- + --- + --- + --- + ---- + ----- + -----
..z.......2......3......4.......5.......6.......7.......8.......9.......10........11
.........z......z.......z.......z........z.......z........z.......z........z..........z
..108...109...110...111...112....113....114.....115....116.....117.....118
+ --- + --- + --- + --- + ---- + ---- + ---- + ---- + ---- + ---- + ----
.....12.....13.....14.....15......16......17......18......19......20.......21.......22
....z.......z........z.......z.........z........z........z.........z........z..........z.........z
..119...120...121...122....49....50.....51....52.....53......54.....55
+ --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + ---
.....23.....24.....25.....26.....27.....28.....29.....30....31.....32.....33
...z.......z........z........z........z.......z.......z.......z.......z........z.......z
....56....57....48
+ --- + --- + ---
.....34.....35.....36
....z.......z.......z
We encrypt this string x1 using a modulus function mod(e,n) where e is the encryption
key and n is an arbitrary number which is relative primitive to e.
x3:sum((getcharn(getchar(x1,i),1))^mod(37,7)/z^i,i,1,string_length(x1)); .....(15).
9409...9604...9801...10000...10201...10404...10609...10816
----- + ----- + ----- + ----- + ----- + ------ + ------ + ------
...z............2.........3..........4..........5............6...........7...........8
...............z.........z..........z...........z............z............z...........z
..11025....11236...11449...11664...11881....12100....12321....12544
+ ------ + ------ + ------ + ------ + ------ + ------ + ------ + ------
.........9...........10.........11........12..........13..........14.........15.........16
.......z............z...........z...........z............z............z...........z...........z
..12769...12996...13225...13456...13689....13924....14161....14400
+ ------ + ------ + ------ + ------ + ------ + ------ + ------ + ------
.......17..........18.........19.........20..........21.........22..........23.........24
.....z............z...........z............z.............z............z............z..........z
..14641...14884.....2401.....2500.....2601.....2704......2809.....2916.....3025
+ ------ + ------ + ------ + ------ + ------ + ------ + ------ + ------ + ------
.......25..........26.........27........28.........29.........30..........31.........32...........33
.....z.............z...........z...........z...........z............z............z.............z............z
.
...3136....3249....2304
+ ------ + ------ + ------
.......34.........35.........36
......z...........z............z
Note that the above ciphertext is already about twice as long as the original plaintext.
The above stream is decrypted back to the original message as shown in equation (16).
x4:sum(numfactor(part(x3,i))^(1/mod(37,7))/z^i,i,1,string_length(x1));.......(16).
97....98....99...100..101...102...103...104...105....106......107
--- + -- + -- + --- + --- + --- + --- + --- + ---- + ----- + -----
..z.......2......3......4.......5.......6.......7.......8.......9.......10........11
.........z......z.......z.......z........z.......z........z.......z........z..........z
..108...109...110...111...112....113....114.....115....116.....117.....118
+ --- + --- + --- + --- + ---- + ---- + ---- + ---- + ---- + ---- + ----
.....12.....13.....14.....15......16......17......18......19......20.......21.......22
....z.......z........z.......z.........z........z........z.........z........z..........z.........z
..119...120...121...122....49....50.....51....52.....53......54.....55
+ --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + ---
.....23.....24.....25.....26.....27.....28.....29.....30....31.....32.....33
...z.......z........z........z........z.......z.......z.......z.......z........z.......z
....56....57....48
+ --- + --- + ---
.....34.....35.....36
....z.......z.......z
4. Conclusions
Thus in this section, it is shown that by starting with the general formulation given
by equation (3), all crytographic systems can be classified neatly by introducing
modifications to this formula.
5 References
The first three papers are directly relevant to the present paper. The remaining
papers may be useful to those who are not familiar with sequence algebra.
1. Schneier Bruce:Applied Cryptography, Protocols, Algorithms, and Source
Code In C, Second Edition, Wiley, pp 29-30.
2. Garfinkel S.:Encryption for Everyone, PGP Pretty Good Privacy,
O'Reilly & Associates, inc. January Ed.: 1995, pp 357.
3. Macsyma: Symbolic/numeric/graphical mathematics software, Mathematics and
System Reference Manual, 16th edition, relevant sections.
4. Sequence Algebra - A Tutorial Paper - Huen Y.K. (Date Released 2/2/98, 46 Kbytes)
Published Papers:
5. Huen Y.K.: A Matrix Map for Prime and Non-prime Numbers, INT. J. Math. Educ. Sci.
Technol., 1994, VOL. 25, NO.6, pp 913-920.
6. Huen Y.K.: Some Interesing Properties Of The Natural Number System, Int. J. Math. Educ.
Sci. Technol., 1996, VOL.27, NO. 5, 685-691.
7. Huen Y.K.: Visual algebra and its applications, INT. J. Math. Educ. Sci. Technol.,
1997, VOL.28, NO.3, pp 333-344.
8. Huen Y.K.: The twin prime problem revisited, INT. J. Math. Educ. Sci. Technol.,1997, VOL.28,
NO. 6, pp 825-834.
9. Huen Y.K.: Is Pie Periodic?, INT. J. Math. Educ. Sci. Technol.,1998,VOL.29,NO.1,19-26. (in the press).
10. Huen Y.K.: Final value theorem in number sequences., INT. J. Math. Educ. Sci. Technol.,199?,VOL.-??,NO.?,???-???. (accepted).
Papers posted in this website.
Comments: References from this point onward are not referred in the
main paper.
Most are provided for readers not familiar with sequence algebra. These papers
can be easily hyperlinked whilst you surf into this URLsite.
========================================================
12. Evaluations Of Normc( ) Function In Macsyma 2.2 - Huen Y.K. (Date Released 17/12/97, 14 Kbytes)
================================================
13. List Processing In Sequence Algebra - Huen Y.K. (Date Released 23/12/97, 20 Kbytes)
================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
22. The Throwing Power Of Oddcomp(z). - by Huen Y.K. (date released : 24.9.97 ) (15 Kbytes).
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
=====================END OF PAPER ======================