Hacker News Reader

Comment by lmm | Hacker News Reader

I don't see such an application; given a number which is known to be a sum of primes it's very easy to reverse this and extract the primes (unlike multiplication, which is how RSA works). And for practical cryptography processes it's always been perfectly reasonable to assume the goldbach conjecture - even though there's no formal proof yet, it's true in such an overwhelming majority of cases that you really wouldn't worry about hitting a counterexample, the odds are far smaller than e.g. a hash collision.

View on HN

If you add three large primes I don't see how you could quickly reverse that process. May be possible that several set's of 3 primes also sum to that number so you would need a process for finding all of them.

Factorisation is unique, the addition of 3 primes is not.

e.g. 29 can be written 5 + 11 + 13 or 3 + 3 + 23

So even if it were a difficult operation to reverse addition of 3 numbers, it would be made easier by collisions.

>Factorisation is unique //

Um, no it isn't.

6, 4 are factors of 24; 2, 12 are factors of 24.

Probably you meant prime decomposition.

I think he means that prime factorization is unique (which is true).

http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmet...

Isn't that what I said?

I could have sworn that last sentence wasn't there (my bad).

Thinking about it more this is basically a special case of the knapsack problem. Which is not obviously impossible, and indeed was used in an early attempt at public-key cryptography, but has since been broken: http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack... .

It was cracked because it depended on a super-increasing sequence, the knapsack problem is still NP-Hard. However, finding a given sequence of primes that sum to the number is not really the knapsack problem.

If I recall correctly, the private key was super increasing. The knapsack encryption algorithm attempted to reduce the super-increasing sequence to a regular sequence. What was broken was that the reduced sequence, while no longer super-increasing, still turned out to be a special case which was easy to solve.

The known prime number - (3 + 5) ?

This is extremely amenable to a rainbow attack - just start here, http://primes.utm.edu/lists/small/1000.txt.

This is less amenable to a rainbow attack than cracking RSA. When cracking RSA you have to factorise a number N into P.Q, so you only have to check up to sqrt(N). With this, you have to get 3 numbers, and check up to N/3.

Reply on news.ycombinator.com