Cryptography question

[Kyriakos]

I read that in the standard US system (RSA), cryptography is based on a few elements tied to primes, including number of co-primes and the Euler function for that (adapted by Riemann for his own bit of mischief later on).
The articles i read state that the system is deemed as safe as long as the larger coprime chosen is large enough (eg it has 30 digits or something), cause the smaller coprime then is one chosen by the computer out of a large enough pool of coprimes to that large number. (co-prime, for those not sure, means a number which is to another number perfectly divided only by 1. Eg 8 and 27 are co-primes, so are 3 and 7, the numbers themselves don't have to be primes).
The Euler zeta function collects all co-primes up to the larger number. It has a few properties still not fleshed out enough for it to be a basis for a modern cryptography system, given the numbers there are sufficiently many in practical cases (large coprime), and the overall sum of the numbers is diverging, ie it doesn't have a limit to a specific number but potentially goes to infinity).

I have a question:

-How does the computer choose the second number? Or (assuming it also chooses the first) what differentiation is there in the routine choosing the second number? Cause if one can guess those numbers then the cryptography collapses (as long as it is not featuring one-off codes as well, which is not practical for a commercial or continuously used system).

Btw, if you are wondering, i need this info so as to direct some nukes at an un-named country situated between the co-primes of Netherlands and Poland.

 

[Leoreth]

Which numbers are you talking about?

In the beginning you randomly generate two primes p, q to calculate the modulus n = pq. The public key element e is coprime to phi(n), but phi(n) is secret, and an attacker cannot calculate it because that requires knowledge of p and q.

So your proposed attack is to guess p or q? RSA is generally not concerned with how they are created (although it becomes vulnerable if they do not satisfy some additional properties). There are cryptographically secure random number generators that are used for this purpose (the standard RNGs of most programming languages are not cryptographically secure), there should be one in OpenSSL for instance. As long as their seeds are secret, there is no way to figure out which keys they have generated. Furthermore, the key generating party does not even have to disclose the type of RNG used for RSA to work.

As for the mechanism behind choosing the e coprime to phi(n), I'm not sure about the principle behind that, and if there is a better approach than just using a random element from a list of coprimes (which in itself looks impractical to calculate). But regardless, this mechanism is not a vulnerability of RSA because phi(n) is kept secret.

 

[Kyriakos]

^

I also miss-named the function to zeta, when it was Phi or Π Euler.

But still its bulk is about that function, which in turn is about groups of co-primes up to a larger integer X.

I was wondering if the computer chooses the numbers in a somewhat known way, cause 'random' is a euphemism when it comes to computers (in someway also for humans, but surely not as notably as with computers)..

You answer is not good, though, cause i still need those nukes.

Btw, on what basis can a 'random' number generator be ever safe from attack/knowing how it works? Unless again it is used as one-off. I mean it is not random literally, and even huge numbers have a finite pool of co-primes, and *maybe* the code for the RNG will tend to produce some pattern (not meant by the coder) more often than not.

 

[Leoreth]

You're right that everything a computer does is deterministic, so a "true" random number generator does not exist, which is why technically we talk about pseudo-random number generators.

However, to predict what a deterministic machine is going to do next (or has done in the past), you need information about its state. As long as that state is kept secret, you have no point of attack. Most computer algorithms are not cryptographically secure in that their output usually reveals at least something about their current state, so that you can derive its state by observing its output over time. Cryptographically secure RNGs are designed not to reveal this kind of information.

Aside from that, there are also "true" RNGs that rely on stochastic outside processes like atmospheric radiation.

Fortunately, if properly used, RSA is safe as long as prime factorization is intractable.

 

[Kyriakos]

You're right that everything a computer does is deterministic, so a "true" random number generator does not exist, which is why technically we talk about pseudo-random number generators.

However, to predict what a deterministic machine is going to do next (or has done in the past), you need information about its state. As long as that state is kept secret, you have no point of attack. Most computer algorithms are not cryptographically secure in that their output usually reveals at least something about their current state, so that you can derive its state by observing its output over time. Cryptographically secure RNGs are designed not to reveal this kind of information.

Aside from that, there are also "true" RNGs that rely on stochastic outside processes like atmospheric radiation.

Fortunately, if properly used, RSA is safe as long as prime factorization is intractable.

There was an old adventure game where a riddle was to produce a number, but it turned out the number was different each time you played. In reality it was tied to the time clock of the computer and... lunar circles that time period

(besides, the Turing team would not be able to break the nazi code if they did not at least have a copy of the enigma machine -they then examined electric circuits used to move some of its parts, using hypotheses elsewhere-. Which in the analogous here would be some educated guess on the type of RNG used, even if a custom one).

 

[Leoreth]

No, that's incorrect. Enigma relied on the encryption mechanism being secret. As soon as its inner workings were discovered, it was much easier to decrypt.

RSA is completely public though, which is why we're able to talk about how it works. The mechanisms behind all commonly used RNGs are public as well. Secret encryption algorithms are the least trustworthy thing there is in cryptography.

 

[Kyriakos]

^The point was what the electric circuits moving the wheels (and other stuff) in the Enigma were the analogous to the 'randomiser' in some other process. Granted that RNG are themselves software (but AFAIK computers still ultimately are based on electric circuits, despite those not being as easy to compute as in some Enigma machine).
Turing, as i read, had to find a way to account for reasonable reduction in the scope of hypotheses on the 'random' part of the Enigma (turning of wheels generated each time the letters of the 'plaintext' were entered) while the encryption is usually thought of as the tie between the 26 letters in the bottom part of the enigma, the 26 letters in the upper part, and the rotors. The circuit is an element of clearly different type there, cause itself rests on properties of electrical systems, not on probabilities and checking hypotheses and leading them to finite and then smallish guesses to check upon.

 

[Leoreth]

I know less about how the Enigma machine actually worked, but it's important to differentiate between the steps of key generation and encryption. The RNG is not involved in the actual encryption process of RSA. It's misleading to consider these two weaknesses equivalent.

Also, even knowing exactly how the RNG used to create the private key works is not sufficient to obtain it, as long as its seed remains unknown.

 

[Zelig]

You're right that everything a computer does is deterministic, so a "true" random number generator does not exist

Sure they do, there are various hardware RNGs that generate true random numbers, and various web APIs for them.

 

[Kyriakos]

Sure they do, there are various hardware RNGs that generate true random numbers, and various web APIs for them.

Much like that arab religious guy with the "if a plane stands perfectly still in the sky" routine

You can't have a machine do 'random' stuff, cause the machine works in some way tied to hardware it has and software along with code. Unknown is not the same as random.

Eg, if you go out your house and find a coin in the third street you enter, it doesn't mean you will find a coin there every other time, or even n times in the future. That event can by and large be termed as 'random', since it has factored in parameters not approachable by you (eg some stranger happened to drop a coin that morning).

In a computer system, though, there is no parameter that external, cause the computer has no peers in the first place. It is an NPC in our MMORPG.

 

[Rashiminos]

The wiki has a good outline:

Key generation

RSA involves a public key and a private key. The public key can be known by everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted in a reasonable amount of time using the private key. The keys for the RSA algorithm are generated the following way:

Choose two distinct prime numbers p and q.
For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length. Prime integers can be efficiently found using a primality test.
Compute n = pq.
n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), where φ is Euler's totient function. This value is kept private.
Choose an integer e such that 1 < e < &#966;(n) and gcd(e, &#966;(n)) = 1; i.e., e and &#966;(n) are coprime.
e is released as the public key exponent.
e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly 2^16 + 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.[5]
Determine d as d &#8801; e^&#8722;1 (mod &#966;(n)); i.e., d is the modular multiplicative inverse of e (modulo &#966;(n)).

This is more clearly stated as: solve for d given d&#8901;e &#8801; 1 (mod &#966;(n))
This is often computed using the extended Euclidean algorithm. Using the pseudocode in the Modular integers section, inputs a and n correspond to e and &#966;(n), respectively.
d is kept as the private key exponent.

The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d, which must be kept secret. p, q, and &#966;(n) must also be kept secret because they can be used to calculate d.

An alternative, used by PKCS#1, is to choose d matching de &#8801; 1 (mod &#955 with &#955; = lcm(p &#8722; 1, q &#8722; 1), where lcm is the least common multiple. Using &#955; instead of &#966;(n) allows more choices for d. &#955; can also be defined using the Carmichael function, &#955;(n).

http://en.wikipedia.org/wiki/RSA_(cryptosystem)

(carets added to show exponentiation.)

 

[Leoreth]

Sure they do, there are various hardware RNGs that generate true random numbers, and various web APIs for them.

Yeah, I was using RNG in a rather narrow sense as software based RNGs. I mentioned later that you can make use of external factors to get true randomness.

The wiki has a good outline:

http://en.wikipedia.org/wiki/RSA_(cryptosystem)

(carats added to show exponentiation.)

It's rather good, but it's unspecific about the process by which the primes are chosen.

(That's not really a flaw of the article because as I said, it doesn't matter for RSA.)

 

[Zelig]

You can't have a machine do 'random' stuff

You can have a machine do fully random stuff, no need for quotes around 'random'.

http://www.idquantique.com/random-number-generation/quantis-random-number-generator/

"Quantis TRNG is a physical random number generator exploiting quantum optics. It is available in USB, PCI and PCI Express versions."

 

[Rashiminos]

Yeah, I was using RNG in a rather narrow sense as software based RNGs. I mentioned later that you can make use of external factors to get true randomness.


It's rather good, but it's unspecific about the process by which the primes are chosen.

In general you get a seed from a {source*} (eg the system clock) and then run a hashing function on the seed until a prime number is returned that satisfies some other properties (eg bit length of the prime).

If you're looking for a more detailed answer: http://csrc.nist.gov/groups/ST/toolkit/random_number.html

source*

On modern computers and servers, key generation software attempts to collect random information from physical sources (often through the underlying operating system): the movements of the mouse, keyboard, hard drive, network events, and other external sources of unpredictable information. However, if the keys are generated from a small set of possibilities, that is, using too little entropy, then the keys may be vulnerable to an attacker. Gathering strong entropy and verifying its strength is a very difficult problem that has given rise to multiple vulnerabilities over the years.

https://freedom-to-tinker.com/blog/...ver-factorable-keys-just-mind-your-ps-and-qs/