Re: -- Crack a simple secret key cryptosystem.

Ulrich Kuehn (kuehn@ESCHER.UNI-MUENSTER.DE)
Mon, 12 Apr 1999 11:58:14 +0200 (MET DST)

• Next message: Thomas Roessler: "Tristrata / Breaking PAL?"
• Previous message: kctang8: "-- Crack a simple secret key cryptosystem."
• In reply to: Mail System Internal Data: "DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA"

kctang8 writes:
> Dear all,
>
> please crack the following system:
>
> Now n denote a positive integer of around 310 digits.
> a,b,c and e denote positive integers less than n.
> e and n are relatively prime.
>
> plaintext: [a,b,c] and n
> encryption: choose a secret number e,
> cyphertext =
> [A,B,C] = [e*a mod n , e*b mod n , e*c mod n]
> decryption: the partner know e, he compute inv = e^(-1) mod n
> get plaintext
> [a,b,c]= [A*inv mod n, B*inv mod n, C*inv mod n]
>
> note: e will be changed for every three numbers [a, b, c].
>
> Does gcd(A,B,C) work fine in this case?
>
First of all, gcd is a function taking two inputs, not three. And it
is defined over the ring Z of integers, not (mod n).

Take a look into Neal Koblitz, A Course in Number Theory and
Cryptography, where a similar scheme is broken by a known plaintext
attack. With chosen plaintext the break is even simpler because you
can rule out the case gcd(a,n) != 1.

Another serious problem I see is the note that e will be changed every
three operations. How will that be done without the decryptor losing
track of the changes?

Hope this helps,
Ulrich

-- 
Ulrich Kuehn ------------------ ukuehn@acm.org
                    kuehn@math.uni-muenster.de
        http://wwwmath.uni-muenster.de/~kuehn/

• Next message: Thomas Roessler: "Tristrata / Breaking PAL?"
• Previous message: kctang8: "-- Crack a simple secret key cryptosystem."
• In reply to: Mail System Internal Data: "DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA"