Hacker News Reader

Comment by MojoJolo | Hacker News Reader

Curiosity. With this 130 page research paper, I'm really curious what's its application in the near future. I'm sure there will be, I'm seeing this in the branch of cryptography.

I'm imagining it to be implemented like a public-private key. Maybe the odd number can be the private key. And three prime numbers can be the public keys. The hash can't be decoded by just the single public key. It needs all three of the public key to decode the hash. Well, with just abrupt thinking, I think it can be more secure? (Not really sure about it though. Just a guess.)

View on HN

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.

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.

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.

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.

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).

Reply on news.ycombinator.com