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 ...
20
No no no! You don't get to pick which key is private and which public. That false sense of freedom is due to
people not understanding that public-key cryptography is conceptually different from ciphers, and
the most popular public-key algorithm RSA being a bijective permutation.
With discrete logarithm for example, your private key is always a scalar ...
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 ...
12
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 strictly 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 ...
9
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 ...
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],
...
9
After generating a key-pair can we pick which key will be private or public?
No, in general we cannot. For most asymmetric cryptosystems the private and public keys are completely different kinds of objects (e.g. one may be a number and the other a point on an elliptic curve), and there's no way to use one in place of the other.
There is, however, one ...
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.
...
8
In RSA encryption and decryption are similar. If you chose e randomly and calculate matching d you could then chose to swap their roles and pick either as the public key.
Usually we don't do this, we pick a small public exponent with few set bits. This makes public key operations much faster.
We can not swap the roles and make the private key operations ...
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 ...
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'
15.3k3 gold badges40 silver badges78 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
44.3k3 gold badges94 silver badges193 bronze badges
6
Use the genpkey command:
openssl genpkey -algorithm x25519
or, for edwards25519:
openssl genpkey -algorithm ed25519
This requires a recent OpenSSL version.
6
The existing answers from DannyNiu and Meir Maor answer well the confusion about whether private and public keys are interchangeable. But it is also worthwhile, I think, to address this snippet from the question:
Having this key pair, I can encrypt a message with my private key and then publish it. That anyone can decrypt the message with my public key ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible