43
No, because these new insights only affect the discovery and patterns regarding finding new prime numbers. In order to break existing encryption algorithms that rely on primes such as RSA, you'd have to have a breakthrough in discovering how to factor integers into primes.
Primes are used in encryption keys as the basis of their generation: two large ...
21
No, because that "discovery" produces nothing of value.
They examined prime numbers up to one billion. In that range, about one in eight numbers ending in 1, 3, 7 or 9 are prime numbers, and which ones are primes is quite unpredictable.
Now if a prime p ends in a digit 9, then the numbers p + 2, p + 4, p + 8, p + 10, p + 12 etc. each have about a one in ...
12
In general, the public and private keys are computed together.
For some schemes, the public key is computed from the private key. ElGamal is an example. (The system parameters include a suitable cyclic group $G$ with a generator $g$. Choose a random exponent $a$. Compute $y=g^a$. The public key is $y$, the private key is $a$.)
For other schemes, this is ...
11
I'll consider that you are using a 256-bit curve per ANS X9.62:2005.
Not all 256-bit bitstrings are a formally valid private key; when using big-endian conventions, these must represent a positive integer less than $n$, the order of the largest prime order subgroup. Quoting the normative A.4.1 Preliminaries in the standard:
An elliptic curve key pair for ...
9
There is consensus that it is safe to use random primes $p$ and $q$ when generating 2048-bit (or wider) RSA public moduli which two prime factors $p$ and $q$ are about half the key size. That is sanctioned by FIPS 186-4, appendix B.3; specifically, wording in B.3.1 item A:
Using methods 1 and 2 [yielding provable (1) and probable (2) random primes],
...
8
There are three ways to look at it:
The mathematics. An elliptic curve key pair is defined as $s, s \cdot G$, where $s$ is an integer, $G$ is the base point and $\cdot$ is elliptic curve point multiplication (scalar multiplication). There is no requirement for $s$ to be smaller than the order of the base point, so you could allow the private key to be ...
8
Well, there are indeed differences between the two standards, as you can see below:
key pair generation
X9.31 requires that $p-1$, $p+1$, $q-1$, $q+1$ all have prime factors between $2^{100}$ and $2^{120}$, and that $p$ and $q$ differ in at least one of the first 100 bits. These requirements are there to frustrate suboptimal factoring methods, and ...
8
This is a tentative guess at answering my own question.
Perhaps the "Fast Prime" method alluded to in the question's citation is that of these two papers (the second polishing the first):
[JPV2000]: Marc Joye, Pascal Paillier, and Serge Vaudenay; Efficient generation of prime numbers, in proceedings of CHES 2000
[JP2006]: Marc Joye and Pascal Paillier; ...
8
Since I am at the source of the original quote, I might as well respond...
Technically, forward secrecy is overhyped because it is recommended almost everywhere. In some contexts it makes sense and is a valuable property. In many other contexts it makes less sense and, while harmless from a security point of view, it may induce performance-related issues.
...
7
One way to do this, if you're working with a multiplicative group $Z^*_p$, is to pick a prime $p$ so that $p-1$ has a large prime factor $q$; once you have this, then to generate a generator of order $q$, you pick a random value $h$, compute $g = h^{(p-1)/q}$, and if that is not 1, then $g$ is a generator of your group.
Obvious questions:
How do you find a ...
7
It you need a deterministically derived key for AES, the DRBG algorithms of NIST SP 800-90A are suitable, and their output is directly usable as an AES key. An example use case is when computing an AES session key from a longer-term master key, and the nonce corresponding to that session.
AES will expand its key (128, 192 or 256-bit) to 128-bit subkeys (one ...
7
The quoted recommendation is generally considered obsolete in the context of RSA with secure parameters, and is either disregarded, or replaced by asking that $\left|p–q\right|>2^{(n/2)–100}$ where $n$ is the number of binary digits for $N=pq$. This modern rule was in ANSI X9.31 (1998), and is still in FIPS 186-4 (2013), appendix B.3, criteria 2(...
7
g^x is the public key of Alice and x her private key, while g^y is the public key of Bob and y his private key.
s=g^(xy) is the shared secret between Alice and bob, that can only be computed by them.
Thus, ElGamal is an asymmetric algorithm computing a shared secret that can be used as a symmetric key.
7
128-bit entropy simply means that we have $2^{128}$ different values to search, which is similar to 128-bit security. For a single target that is impossible since even the collaborative powers of Bitcoin Miners can reach $\approx 2^{92}$ in a year. Therefore one needs $2^{35}$ years to find the correct password. The iteration of PBKDF2 is 2048 so, we need to ...
6
Symmetric keys don't need to be in any particular format -- they're just a sequence of (pseudo)random bits.
Most programming environments provide some sort of "secure random" mechanism (a CSPRNG). You can use this to acquire a byte array of the appropriate length (e.g. 32 bytes for AES256), which can be used as a key. Be sure to pass in the raw bytes, and ...
6
The reason that one must be derived from the other is that the private and corresponding public key are strongly related: For instance, in RSA, the pair satisfies $ed\equiv 1\mod\varphi(n)$; in Diffie-Hellman, we have $A=g^a$; and so forth. Hence, it is just natural to start with with generating one part and deriving the other to satisfy the cryptosystem's ...
6
Not really - the frequency of primes doesn't change, and it's not a certainty that any given prime isn't followed by another with the same final digit. You'd still have to check all possible primes in the appropriate range, but you could slightly optimise the order of checks. However, given the number of digits in primes used in key based ciphers, there are ...
6
If you choose $p$ and $q$ at random of the same length, then they will be far away from each other with extraordinarily high probability. Thus, this is not an issue.
In the past, there were those that recommend safe primes to make sure that neither $p-1$ nor $q-1$ would have all small factors. However, this isn't necessary (and is now not even recommended). ...
6
No, your values for $e$ and primes are fine (well, at least for a toy example); $e$ is relatively prime to both $p-1$ and $q-1$, and that's the only hard requirement (not counting the security related ones, of course).
I get $d=905$, as $5 \times 905 \equiv 1 \pmod{ \operatorname{lcm}((53-1),(59-1))}$; alternatively, you might get $d=2413$, if you do the ...
6
Applications that generate key get the randomness (entropy) from the operating system. The operating system, in turn, gets the randomness where it can find it. Ideally the OS gets randomness from a proper hardware generator, which is present in modern PC and smartphone processors. These hardware generators are based on physical phenomena that are not ...
answered Apr 24 '17 at 21:40
Gilles 'SO- stop being evil'
14.7k3 gold badges40 silver badges76 bronze badges
6
RSA public/private key pairs are no exception: there is no way to assess that a cryptographic key is strong by looking at its value; only ways to assess that it is weak. And lack of signs that it is weak is no good indication that it is strong. Arguments are extensions of:
A key which value leaked is totally weak, and has exactly the same value as before it ...
6
Given the information in the question and in the comments, this is pretty straightforward:
Online phase: Use any common key agreement protocol, e.g. Diffie-Hellmann key exchange to generate a shared secret.
Offline phase: Use a proper key derivation function on the shared secret and a nonce - one nonce for each key you need to generate. A counter would ...
6
A NIST P-256 secret key (for ECDH or ECDSA) represents any scalar modulo $\ell$ for $$\ell = 2^{256} - 432420386565659656852420866394968145599,$$ whereas an X25519 secret key represents an integer multiple of 8 between $2^{254}$ and $2^{255}$, interpreted as a scalar modulo $8 p_1$ for $$p_1 = 2^{252} + 27742317777372353535851937790883648493.$$ In both ...
answered Mar 16 '18 at 20:14
Squeamish Ossifrage
43.8k3 gold badges90 silver badges187 bronze badges
5
No, it's not a problem.
What you've found is known as the square computational diffie-hellman problem(SCDH) and it can be shown that this is equivalent to the computational diffie-hellman problem(CDH).
For completeness:
SCDH:
Given $g$ (your $G$) and $g^x$ (your $Q$), find $g^{x^2}$ (your $d_A^2G$).
It is shown here that this problem is as hard as the ...
5
Even with perfectly random input, if your final key size is 32 bytes, you cannot have more than 32 bytes of entropy in it.
But it seems pretty useless to use key stretching if you already have more random bytes than your key length, you could just use 32 bytes of your 'perfect' source as an AES key. You just expose yourself to possible weakness in the key ...
5
Why else are ephemeral keys used?
Ephemeral keys are not a specific form of keys, they are just short lived keys within a key establishment protocol. Usually they are not directly trusted as they are generated on the fly.
ECIES may also use an ephemeral private key, to name a single other usage.
In particular, if I don't care about Perfect Forward ...
5
I assume your TRNG has a uniform distribution and can generate all possible 32bit numbers (ie. isn't limited to a specific smaller number range, just to [0,2^32-1]).
In this case, it doesn't really matter, because the TRNG output is also a stream of truly random single bits, as well as a stream of truly random 2bit pairs (numbers 0-3), etc.
If this were not ...
5
Is it mainly for validation purpose to ensure that the input key size is correct. So, for e.g. if algorithm is AES, the key length has to be 128, 256 or 192.
Yes, indicating a name to an algorithm may be used to check for valid generation parameters, including the key size that is generally present.
For Java - the principal language assumed in the initial ...
5
Use the genpkey command:
openssl genpkey -algorithm x25519
or, for edwards25519:
openssl genpkey -algorithm ed25519
This requires a recent OpenSSL version.
4
Modular inverse can be computed with Extended Euclidian Algorithm, as other answers suggest.
I will answer your second question - why an attacker can't get private key? The problem here is that the private exponent is the modular inverse of the public one, but modulo $\phi(n)$, not $n$:
$d \equiv e^{-1} \pmod{\phi(n)}$
Attacker does not know $\phi(n) = (p-...
Only top voted, non community-wiki answers of a minimum length are eligible
