Say I pick modulus $m=2633$ and key $e=13$

My private key $d$ is $13$ inverse in $\bmod 2632$ which I need to compute

$(e,m)$ is my public key that anyone can use to encrypt message for me and then send it to me as:

encrypt message: "TH" ($T=19, H=07$) as $1907^{13} \bmod 2633$

but since $(e,m)$ is public anyone can compute my private $d$ using EEA

so where is the security? I know I do not understand this, could anyone explain?

  • 2
    $\begingroup$ $d$ is the inverse modulo $\varphi(n)$, not modulo $n$. $\endgroup$ – CodesInChaos May 27 '16 at 20:55
  • 1
    $\begingroup$ 2633 is obviously an invalid choice if you want security, because as you already noted it's trivial to calculate $\varphi(n)$ ($\varphi(n)$) for it. You need to chose a modulus which is a composite (preferably of two primes). Funfact: It may be heard to recover your message "TH" from "1907" as this may not be a unique encoding for certain integers. $\endgroup$ – SEJPM May 27 '16 at 21:09
  • 1
    $\begingroup$ Are you trying to understand Diffie–Hellman key exchange? Or the RSA public-key cryptosystem? Or some other system? $\endgroup$ – David Cary May 27 '16 at 21:12
  • 1
    $\begingroup$ OK, if you want to do RSA, your public key is $e,n$ where $e$ is the public exponent and $n$ is a composite number. If you want to do an exponentiation based cryptosystem your public key would be some integer $g$ (which upon exponentiation generates a large group), a prime $p$ (such as your 2633) and some $\beta$ which is constructed as $\beta=g^a\bmod p$ $\endgroup$ – SEJPM May 27 '16 at 21:18
  • 2
    $\begingroup$ What is "exponential cipher"? If it's just exponentiation modulo a prime, there is absolutely no hope of obtaining any kind of security. $\endgroup$ – fkraiem May 28 '16 at 3:29

Exponential cipher is a symmetric-key algorithm, not public-key one. So you don't have any public and private keys. You only have one secret key and it's used for encryption of messages between people that know the key.

The security of exponential cipher is not in the computiation of $d$ from $e$, which is easily computable by EEA as you said. The security of this cipher lies at the principle of discrete logarithm problem, as well as Diffie-Hellman key exchange does.

The principle:

You have prime modulus $m = 2633$, secret key $e = 29$, where $\gcd(e,\ m-1) = 1$ so $e$ has inverse $\textrm{mod}\ m-1$ and you can compute your key $d$ for deciphering:

$d = |e^{-1}|_{m-1} = |29^{-1}|_{2632} = 2269$

The only thing you have to keep secret is the key $e$.

The encryption pattern is ($c$ for ciphertext block, $p$ for plaintext block) :

$c = |p^e|_m$.

So you can encrypt "TH" (T=19, H=07) as $c = |1907^{29}|_{2633} = 2199$.

To decrypt:

$p = |c^d|_m = |2199^{2269}|_{2633} = 1907$ = "TH"

Discrete logarithm problem:

Consider a possible attacker who has modulus $m = 2633$, block of ciphertext $c = 2199$ and corresponding block of plaintext $p = 1907$. What does he know:

$c = |p^e|_m$

$2199 = |1907^e|_{2633}$

which means $e =|\log_{1907}{2199}|_{2633}$

The discrete logarithm problem says that it's not possible to compute the key $e$ from this equality in reasonable time (for higher numbers of course).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.