Re: A New Encryption Algorithm

Unruh wrote:
> healyd@classicnet.net writes:
>
> >In protest of the NSA, I am submitting to you my newest math success:
> >The Sons of the Tsars encryption algorithm. This is being donated into
> >the public domain. This algorithm is faster than the Rabin Algorithm
> >and might give RSA a run for its money.
> >Choose any two primes such that a=b=5 mod 12. Let n=b mod a and c be
> >the cipher text and x be the plaintext. c=x^3 mod n. x=c^((a+1)/6)
> >mod n=c^((b+1)/6) mod n.
>
> So I choose b-a=12 (yes I am pretty sure that there are two such primes
> such that a mod 12=5 and b=a+12 is also prime). Then n is 12 and the
> encryption algorithm is trivial to break. (x must be less than 12 for there
> to be a unique relation between x and c, and searching through 12 messages
> is not hard. )

He wrote a=b=5 mod 12 which means a and b are congruent to 5 mod 12.

So let's pick a = b = 17 :-) a mod b is 0, so n=0, c=x^3 mod 0 ...
well that's not really defined.

so let's pick a = 29, b = 17, then we have n = b mod a = 17. That's a
prime ... so computing x^1/3 is trivial.

Let's pick a = 17, b = 29, then n = b mod a = 12. Now let's encrypt
x=5, c is 125 mod 12 ==5 [oddly enough...] now 5^a+1/6 is 5^30/6 == 5^5
== 3125 == 5 ... wow it works :-)

So clearly we have several requirements.

1. a > b
2. a mod b cannot be smooth [or prime]

The second will cause problems. Without knowing the factorization of a
mod b you can't tell if it's factorable, more importantly you can't
tell what the smallest non-trivial prime factor is without essentially
attacking it.

I don't see a direct way to produce a mod b with known non-trivial
factorization.

Tom
Received on Tue Jan 17 16:50:26 2006