[David Cooper (OP)]

There's been a lot of talk about the damage done by Snowden with terroists and criminals being more careful to communicate by means involving secure encryption, but I can't see any real security for them in that. Where can they get their prime numbers for other than the security services who will be all over the net pretending to be other kinds of organisations interested in privacy? Even if some of those organisations aren't run by any of the security services, wherever you download prime numbers from, it will be known which ones you have access to and should be very easy to work out which pair of them have been used to create your public key. Suppose you download a billion of them and then some means of selecting two of them is made at random, it would be an easy task to work out which of those billion prime numbers have been used, an ordinary computer only taking a few seconds to work that out (by multiplying each in turn by a few of the others until they find the point where one result is less than the public key and the next is greater than it).

The only way round this I can think of for now is that your computer would have to find large prime numbers all by itself, perhaps by starting at some random value and then hunting upwards from there until it finds one. Even then, though, there's the problem of holes in the operating system allowing the security services to look straight into your machine and to see the message before you've encrypted it (or after you've decrypted it).

When you realise how futile it is to try to communicate privately, the only sensible thing for any terrorist or criminal to do is give up and go and live a normal life instead.

[RD]

... When you realise how futile it is to try to communicate privately, the only sensible thing for any terrorist or criminal to do is give up and go and live a normal life instead.

The terms of the RIPA , (Regulation of Investigatory Powers Act), suggest that UK government cannot crack all encryption ...

Part 3 of the Regulation of Investigatory Powers Act 2000 gives the police powers to order the disclosure of encryption keys, or force suspects to decrypt encrypted data. Anyone who refuses to hand over a key to the police would face up to two years' imprisonment. Under current anti-terrorism legislation, terrorist suspects now face up to five years for withholding keys.

https://wiki.openrightsgroup.org/wiki/Regulation_of_Investigatory_Powers_Act_2000/Part_III

Brute-force* attacks can take unfeasibly long amounts of time if a password is long and random ...

 [ Invalid Attachment ]
https://www.grc.com/haystack.htm

[ * unless the brute-force is rubber-hose cryptography []  ]

[CliffordK]

The terms of the RIPA , (Regulation of Investigatory Powers Act), suggest that UK government cannot crack all encryption ...

Part 3 of the Regulation of Investigatory Powers Act 2000 gives the police powers to order the disclosure of encryption keys, or force suspects to decrypt encrypted data. Anyone who refuses to hand over a key to the police would face up to two years' imprisonment. Under current anti-terrorism legislation, terrorist suspects now face up to five years for withholding keys.

https://wiki.openrightsgroup.org/wiki/Regulation_of_Investigatory_Powers_Act_2000/Part_III

There is some debate in the USA about whether or not passwords are protected under the fifth amendment.

No person shall be [...] compelled in any criminal case to be a witness against himself...

I doubt the RIPA would hold up to scrutiny in the USA.  And, since the prohibition against self incrimination clause is in the constitution, it couldn't be changed without a new amendment to the constitution which is unlikely.

As far as primes, if your entire key is based on a one in a billion chance, it could be cracked in about a second.  However, if you required several primes, then you may be able to multiply that out (billion)ⁿ decryption steps for a unique set of n prime keys, as long as the keys could not be uniquely sequentially decrypted, which would put you back at the order n*(billion), and back to about a second for the decryption for small values of n.

The trick, of course, is making sure your password, key, whatever is protected. 

Some encryption algorithms are supposed to be one-way.  For example UNIX encrypted passwords.  Keep the encrypted password, and probe the password table with a newly encrypted password.  However, that may not in fact be the case.

[CliffordK]

As far as sequential decryption.
Consider the difference between 1 combination lock with 5 tumblers (and 10 digits), vs 5 combination locks, each with 1 tumbler and 10 digits.

In the first case, you have 10*10*10*10*10, or 10⁵ combinations, or 100,000 unique combinations.

In the second case, each lock has 10 combinations, or a total of 10+10+10+10+10, or 5*10, or 50 steps to open the lock.

Attempts to pick your combination lock undoubtedly rely on trying to force the lock from the first case to the second case.

[evan_au]

Computers at each end of the session pick their own prime numbers at random, rather than download them, so they can't be directly snooped by a third party. The numbers from each end of the conversation are then combined in such a way that a snooper does not see either prime number in unencrypted form.

It is impractical (with current published technology) to factor a product of large primes, or even to definitively prove that a given number really is prime. So your home computer and network servers typically uses a method like this:

• Create/lookup a table of the first million prime numbers (these are no secret)
  
• Generate a really big random number
  
• Try dividing the really big number by each of the million prime numbers. If it is a multiple, go back to step 2
  
• There is a "pseudo-primality" test, which does not prove that a number is prime, but gives a high confidence that it is prime (eg failure rate of 1 in 1 billion). Run this 50 times; if it fails, go to step 2.
  
• When you reach this point, you have a large number which is almost certainly prime.

The above procedure is fairly solid - but it has several shortcomings:

• Where do you get the original random number from? If it is from a 16-bit "seed", there are only 65536 possible large random numbers that can be generated, not the huge quantity you might expect.
  
• Snowden mentioned that the security agencies had participated in standards development to weaken the standard level of encryption (eg the number of bits used)
  
• Security agencies had worked with implementers of the standard to weaken the implementation of the encryption
  
• Security agencies could requisition the encryption keys used in a session. Once you know the prime numbers from one end, you can read the entire exchange.

Note: Quantum methods potentially provide breakthrough methods in factoring large numbers, but this field has fallen rather silent after publishing the factors of 15 and 21. There are undoubtedly many teams working on it.

Unfortunately, I don't think this is enough to persuade your average would-be terrorist to get a real job...

[RD]

Security agencies had worked with implementers of the standard to weaken the implementation of the encryption

Having read that this now makes sense ...

BlackBerry software uses only one PBKDF2 iteration, thus not taking advantage of the key security features of PBKDF2.
By contrast, according to Katalov, Apple's iOS 3 uses 2,000 iterations and iOS 4 uses 10,000

http://en.wikipedia.org/wiki/PBKDF2#BlackBerry_vulnerability

[David Cooper (OP)]

Computers at each end of the session pick their own prime numbers at random, rather than download them, so they can't be directly snooped by a third party. The numbers from each end of the conversation are then combined in such a way that a snooper does not see either prime number in unencrypted form.

It is impractical (with current published technology) to factor a product of large primes, or even to definitively prove that a given number really is prime. So your home computer and network servers typically uses a method like this:

• Create/lookup a table of the first million prime numbers (these are no secret)
  
• Generate a really big random number
  
• Try dividing the really big number by each of the million prime numbers. If it is a multiple, go back to step 2
  
• There is a "pseudo-primality" test, which does not prove that a number is prime, but gives a high confidence that it is prime (eg failure rate of 1 in 1 billion). Run this 50 times; if it fails, go to step 2.
  
• When you reach this point, you have a large number which is almost certainly prime.

That's exactly what I wanted to know - the key part of the explanation missing from the accounts of public-key cryptography that I've been reading.

Unfortunately, I don't think this is enough to persuade your average would-be terrorist to get a real job...

As long as the more intelligent ones give up, the stupid ones don't matter as they'll make no end of mistakes anyway. To get round the problem of holes in the operating system letting outsiders see straight into your machine and reading the plain text versions of your messages, you'd need to write and encrypt them on another machine that's never connected to the internet, and then you'd have to transfer the encrypted versions of messages to and from them using some means that will prevent viruses getting into your isolated machine, which isn't easy. If you manage to find a secure way to do it, you're then going to be drawing attention to yourself because an outsider exploiting a hole to look into your connected machine will see that you're going to extreme lengths to encrypt and decrypt your messages on an isolated machine, and normal people simply don't do that. Big businesses might, but normal people in their homes do not. It's like sending a message to the NSA that you're up to something and that they should be spying on you. I suspect that the security agencies are very happy about the way things are going because terrorists and criminals are now attracting more attention to themselves by using encryption while their communications can still be read in full. Most of the programs providing encryption for them will have been written by the NSA too.

Note: Quantum methods potentially provide breakthrough methods in factoring large numbers, but this field has fallen rather silent after publishing the factors of 15 and 21. There are undoubtedly many teams working on it.

It'll be a pity if we don't get to hear how big the numbers can go with it still working, because if there's a physical limit to how many superpositions the universe can sustain at once, we might not be told about it for a long time.