cat Diophanencrypt
DIOPHANTINE ENCRYPTION FOR PUBLIC KEY ENCODING

General Introduction

Articles dealing with public key codes frequently assume the user requires
enormous levels of
security with correspondingly large and difficult computations to transform
plain text into secure text. This then leads to a requirement for special
processing which is not readily available to the general user.
Motivated by a desire to make the process of
public key encryption more accessible, I began by selecting a somewhat more
restricted objective than that implied as the standard for security currently
reported.  First, it seems more logical that a public key code technique is
most effective when used to address the problem of key distribution.
For this and many other forms of encryption, the ability to quickly
disseminate new keys would provide enhanced security.  The explorations
reported in this paper took this need as its primary requirement.

This bounding of the objective alone does not restrict the problem
enough to make the public key technique as accesible.  Some
further restriction is necessary.  It is assumed that if a password or short
key is the information being distributed, there is no point in achieving
more security for its transmission than is inherent in the system that is being
protected. Accordingly, if a six digit numeric sequence is the cleartext, and
the use of this numeric sequence is such that successive attempts involving its
one million possible values would lead to its decryption, then the public key
component of the process need not involve code spaces requiring years to
search.  On the other hand, since we have proposed that public key codes be
used to protect the channels along which keys or passwords are passed,
it does seem desirable that the public key code avoid the situation where it
becomes easier to attack that channel than attempt to decrypt the channel the
password or key itself is intended to protect. It is within this general
framework of need, that the following concept was developed.

Mathematical foundation.

        z = ax + by
        cz = acx + bcy
        if ac = 1 mod d
        and bc = e mod d
        then x = cz mod d mod e

Operational arrangement
In setting up the public key arrangement, values of c, d, and e are chosen and
kept secret.  They are used to calculate a and b and will be used later to
invert the encryption of x.
        Values for a and b are published. To encode a value x, a number y is
picked at random.  Using x and y in the equation z = ax + by, the value of z
becomes the encrypted message, corresponding to x. Any receiver who knows c,
d, and e can determine x by using the relationship: x = cz mod d mod e.
Anyone knowing z, a and b can only determine x by an extended and difficult
analysis.

Numerical example

The following example was developed and tested using bc, a Unix utility which
provides unlimited precision integer arithmetic.

Let c = 4978425243852 and d = 17838619569241 and e = 4223579.
Given these values, a is required to be the modular inverse of c mod d.
This result gives a = 8480320057465.
Also, b = a * e mod d = 11567267856144.
Trying these values out, give x a value to be encrypted.  Say x = 223124.
Assign y a value at random.  For illustration say y = 123456.  Combining x and y
through straight ( not modular) multiplication and addition gives the
result z = 3320203072629876859.
Recovering x is done with modular multiplication.  First c*z mod d and then the
evaluation of this result mod e gives back 223124.

Computational lab

Performing these long products and sums, especially with large moduli is tedious.
For the situation where the user has access to Unix and bc, a script called
diophanlab has been created to be used as an argument for the bc command.
With diophanlab as its argument, the command bc will put a user in the bc
environment with prestored values of c, d, and e.  Using the
pre-stored invert algorithm, i(x,y) the user can then generate a and b. The user can
then try out the encryption and decryption process.
The following is a journal of the transactions after 'bc diophanlab'

c
4978425243852
d
17838619569241
e
4223579
a = i(c,d)
a
8480320057465
b = a * e % d
b
11567267856144
z = a * 123456 + b * 654321
z
8615652663914397264
x = z * c % d % e
123456
control d (to exit bc)

Cryptoanalysis

The process and examples are, by no stretch, secure public key codes.  While
a lock may be easily broken by a professional thief, it none-the-less provides
an essential level of security  by merely forcing the serious thief to take
his dishonesty seriously. Similar standards are appropriate here.
Cryptoanalysis, in this instance must take the approach of quantifying the
relatively modest difficulties imposed by various levels of discretion.
A general solution is given in the report "THE CRYPTOGRAPHIC SECURITY OF COMPACT
KNAPSACKS" by Adi Shamir (MIT Industrial Liason report # 30491) When applied to
the example and arrangement described here, the general solution converts to
the specific solution:
        If      u = 57085100566029168674946029747639950585
        and     v = 41850844065599483614044717186227245771
        Then    x = u * z + a * t
        and     y = v * z - b * t
The coefficients u and v are generated by a process which follows the general
method of Euclid's algorithm, knowing only a and b. (it helps to realize that
a * u - b * v = 1, a fact that is not easily verified, given the size of u
and v.)

Proposed Avenues of Research

Signatures
The diophantine encryption processin some ways, more closely
resembles the RSA system(based on prime numbers) rather than the Merkle
and Helman system (based on knapsacks). Hopefully, then diophantine encryption,
like the RSA system can provide for signatures.

Improved security
Symmetry suggests that a trapdoor based on x = g * (c * z mod d) mod e imposes
one additional unknown and thus, it would seem, adds to security without
inelegance. On the other hand, a glance at the expression reminds one that any
combination of g and c' which mod d mod e equals c, is equivalent.  Thus adding
g to the list of secret variables does not increase security.  Or does it?
Are there other ways to effect elegant extensions to the system's security?

Appendix

Listing of the bc script diophanlab:

c = 4978425243852
d = 17838619569241
e = 4223579
define i(x,y) {
auto a, z
z = 1
while(x > 1) {
a = ( y / x ) + 1
x = a * x % y
z = z * a % y }
return(z)
}

Listing of the bc script crackscript

a = 8480320057465
b = 11567267856144
define g(x,y) {
auto z
z = x
while(z > 1) {
z = y % x
y = x
x = z
}
return(x)
}
define i(x,y) {
auto a,  z, w
w = y
z = 1
while( x < w) {
                a = ( y / x ) + 1
                w = x
                x = a * x % y
                z = z * a % y
}
return(z)
}
$