IJPAM: Volume 5, No. 2 (2003)

A PUBLIC-KEY CRYPTOSYSTEM BASED ON
DIOPHANTINE EQUATIONS

Mohammad Bagheri$^1$, Nader Dastranj$^2$, Gholamreza Jandaghi$^1$
$^1$Department of Mathematics
Imam Hossein University
P.O. Box 16895/198, Tehran, IRAN
$^2$Payame-Noor University
Orumieh, IRAN


Abstract.The classical cryptography has been replaced by Public-Key cryptography since the past two decades. One of the most poular system proposed by Merkle and Helman named as the Knapsack-Public-Key-Encryption in 1978 [#!1!#]. This system of cryptography is based on the concept that if $C$ is a known number, how we can choose some numbers from a set so that they are summed up to $C$ in mode $M$. This system was broken by Shamir [#!2!#] six years after its genesis. In this paper, we present a new Public-Key cryptosystem. In this system, the equation $\sum_{i=1}^n a_ix_i=C$ is solved in mode $M$, in which $C$ and $a_i$ are known and $x_i\in \{0,1,2\}$. It can be simply seen that in general case we need to investigate $2^n$ combinations, while in our system, one needs to examine $3^n$ combinations which means that the security of the new system is higher than that of Merkle's.

Received: December 22, 2002

AMS Subject Classification: 94A60

Key Words and Phrases: Public-Key, cryptosystem, Diophantine equations

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2003
Volume: 5
Issue: 2