Hot answers tagged public-key
14
From the definition of the totient function, we have the relation:
$$\varphi{(n)} = (p - 1)(q - 1) = pq - p - q + 1 = (n + 1) - (p + q)$$
It then easily follows that:
$$(n + 1) - \varphi{(n)} = p + q$$
$$(n + 1) - \varphi{(n)} - p = q$$
And you know from the definition of RSA that:
$$n = pq$$
Substituting one into the other, you can derive:
$$n = p ...
14
A Mersenne prime is a prime number that can be written in the form $M_p = 2^n-1$, and they’re extremely rare finds. Of all the numbers between 0 and $2^{25,964,951}-1$ there are 1,622,441 that are prime, but only 42 are Mersenne primes.
The second sentence is wrong.
What they meant to say is that there are 1,622,441 numbers of the form they mentioned ...
9
The main difference is that Pohlig-Hellman is a symmetric cypher, while RSA is a public key system. This is because, with Pohlig-Hellman, anyone who knows the encryption key $e$ can compute the inverse operation (because the 'decryption' key $e^{-1} \bmod p-1$ is easy to compute), while the RSA, someone who knows the encryption key $e$ (but not the ...
9
There's an obvious solution using DH: Alice has a private key $a$ and a public key $g^a$; Bob has a private key $b$ and a public key $g^b$.
When Bob sends a message, he computes the shared secret value $(g^a)^b$, converts that into a MAC key (possibly using a nonce to prevent key reuse), computes the MAC of the message, and sends the message and the MAC ...
8
Using $e\ne65537$ would reduce compatibility with existing hardware or software, and break conformance to some standards or prescriptions of security authorities. Any higher $e$ would make the public RSA operation (used for encryption, or signature verification) slower. Some lower $e$, in particular $e=3$, would make that operation appreciably faster (up to ...
8
Yes, this thinking is correct; there is no requirement that the public exponent $e$ to be random. After all, it doesn't matter whether $e$ can be guessed by an attacker; we'll be including that value in the public key anyways.
Common practice is currently to use the fixed value $65537 =2^{16} +1$ for $e$. Any odd value of $e > 1$ will work; however, ...
8
Post-quantum security: As you note, quantum attacks are not known to break lattice-based cryptosystems. But some other proposals like McEliece, as well as most symmetric primitives are not known to be poly-time breakable on a quantum computer.
Security from worst case assumptions: In security proofs for cryptosystems we typically assume that some problem ...
7
Yes. Such proofs are possible for El Gamal.
It involves a zero knowledge proof of equality of a discrete log, together with the homomorphic property of El Gamal encryption.
Recall that given $E(a)$ and $E(b)$, anyone can form $E(a/b)$ using the homomorphic property of El Gamal. Suppose $E(a/b)=(r,s)=(g^k,h^k a/b)$ (where $g$ is the generator and $h$ is ...
7
There are two main reasons why asymmetric cryptography is practically never used to directly encrypt significant amount of data:
1) Size of cryptogram: symmetric encryption does not increase the size of the cryptogram (asymptotically), but asymmetric encryption does. If we take the example of RSAES-OAEP in PKCS#1v2 with a 1024-bit key and 160-bit SHA-1 ...
7
No, the public and private exponents will never be the same for real (that is, not toy) RSA keys.
The public exponent is almost always be deliberately chosen as a small value (with 65537, 3 and 17 being the most popular choices). In contrast, the private exponent will always be a huge value; always at least $(p-1)/e$ (where $p$ is the larger prime factor ...
7
An alternative:
Client generates preliminary keypair $(t, T)$ with $T=tB$
Clients sends $T$ to server
Server sends a random scalar $n$ back(alternatively choose $n = \mathrm{HMAC}(k, T)$ with secret key $k$), and assigns the public key $A = T + nB$ to the client
Client uses $a = t+n$ as private and $A$ as public key.
That way the server decides the ...
7
For your application: "I need the (underpowered 8-bit) slave to be able to tell if a command issued is really trustable", RSA signature with low public exponent ($e=3$), or Rabin (an analog with $e=2$), is likely the most appropriate, assuming you can't trust the slaves to keep a key secret, which is the only realistic assumption unless that slave uses ...
7
The $1^k$ is a formalism that's only there to make the theoreticians happy. You can safely ignore it. When you actually implement the cryptosystem, you don't try to pass the string $1^k$; instead, you pass $k$, the security parameter (a representation of how much cryptographic strength is desired from the key generation algorithm).
I wish I could leave it ...
6
It's not possible.
The number of primes smaller than $x$ is approximately $\frac{x}{\ln x}$. Therefore the number of 512bit primes (approximately the length you need for $1024$ bit modulus) is approximately $\frac{2^{513}}{\ln 2^{513}}-\frac{2^{512}}{\ln 2^{512}} \approx 2.76×10^{151}$.
The number of RSA moduli (i.e. pair of two distinct primes) is ...
6
The $2^{16} + 1$ exponent is really meant for use in real life systems, in which public keys are expected to be considerably larger than that. I guess CrypTool assumes this is the case, as you would expect, really.
That said, if $\gcd{(e, \varphi{(n)})} = 1$, then $gcd{(e ~ \mathrm{mod} ~ \varphi{(n)}, \varphi{(n)})} = 1$ by definition, so such an $e$ will ...
6
If you know $\phi(n)$ it's trivial to calculate the secret exponent $d$ given $e$ and $n$.
In fact that's just what happens during normal RSA key generation. You use that $e \cdot d =1 \mod \phi(n)$, and solve for $d$ using the extended Euclidian algorithm.
Wikipedia about RSA key generation:
Determine $d$ as:
$d = e^{-1} \mod \phi(n)$
i.e., $d$ is ...
6
It is probably not the case of your example, but in some sense "asymmetric hash functions" do exists: they are called trapdoor hash functions (or also chameleon hash functions).
Very briefly, they are collision resistant only if you don't know their trapdoor secret key.
Such functions take 2 arguments (instead of the usual one), and the second argument is ...
6
Symmetric encryption and asymmetric encryption algorithms are built upon vastly different mathematical constructs.
In typical symmetric encryption algorithms, the key is quite literally just a random number in $\left[0 .. 2^n\right]$, where $n$ is the key length. The strength of the key is based upon its resistance to brute-force attacks, where an attacker ...
6
The Diffie-Hellman key exchange is a public-key technology. It is (by itself) not an encryption algorithm (or signature algorithm), though.
Here is the basic function: (All calculations here happen in a discrete group of sufficient size, where the Diffie-Hellman problem is considered hard, usually the multiplicative group modulo a big prime (for classical ...
6
You don't need to know $m$. You know $m^3$ modulo each modulus, which is sufficient. You want to find:
$$c \equiv m^3 \pmod{n_b}$$
$$c \equiv m^3 \pmod{n_c}$$
$$c \equiv m^3 \pmod{n_d}$$
Because $n_b$, $n_c$, $n_d$ are pairwise coprime (assume they have no common factors) a solution must exist.
The Wikipedia page has a nice explanation of the algorithm ...
5
A slightly more efficient method to perform decryption would be:
Compute $r^e = (y^d)$
Find the multiplicative inverse $r^{-e}$ of $r^e$ modulo $n$
Compute $m = (r^{-e} \cdot z)^d = (r^{-e} \cdot r^e \cdot m^e) ^d$
This has two computations of $x^d$ for some $x$; your method has three.
On the other hand, this doesn't address your question; if $r^{-1}$ ...
5
Well, reusing a key isn't a problem; after all, RSA keys are generally used many times.
However, if you fix the padding, there does exist one other potential problem; message malleability.
To example, suppose Alice sends two messages to Bob, $X_1, X_2$ and $Y_1, Y_2$. To send these, Alice actually sends:
$E(X_1), E(X_2)$
$E(Y_1), E(Y_2)$
Now, Eve can't ...
5
As fgrieu notes, the problem as specified is unsolvable: if the server alone should not be able to decrypt the files, then there must be something (in this case, the password) possessed by the user but not the server which is needed to decrypt them. If the user loses this extra information, there's no way the server can provide them access to the files ...
5
None.
When enciphering any small set of values (including a fair coin flip, a byte, even a small password..), unpadded RSA (or RSA with any padding that does not include randomness) is a terminally weak encryption method: the adversary can enumerate the possible plaintext values, encrypt them using the public key, and check against the ciphertext to ...
5
The idea that cryptography alone can provide non-repudiation is a myth. I realize it is one that is taught in many crypto textbooks -- but the textbooks are wrong.
See, e.g., my answer here and here.
I could suggest some constructions (e.g., sign the message, append the signature to the message, then encrypt it using an authenticated encryption mode of ...
5
To get non-repudiation, you must have a "proof" which can be used against the signer himself. Symmetric cryptography, by itself, will not help you there, because a cryptographic proof can only come from some "secret" which is under exclusive control of the signer, and the symmetric model assumes that there is a shared secret between two entities. The concept ...
5
INT-CTXT and INT-PTXT are usually on considered for private-key encryption. For public-key encryption, no correct encryption scheme can satisfy those requirements. (Proof: The adversary can run the encryption algorithm on an arbitrary message and submit it as its output. Since it made no queries to its encryption oracle, this ciphertext violates both ...
5
Hashes like SHA-x are symmetric and unkeyed. I have never heard of asymmetric hashes.
Your question is based on a misunderstanding. You can implement computations in an asynchronous fashion, where you request some computation, then your thread is free to do something else, and at some later point when the computation is finished you do something with the ...
5
For ElGamal to be secure, the 'discrete log problem' (which is, given $g$ and $g^x$, find $x$) must be intractable. You give a generic way to attack the discrete log problem for a group with $n$ elements with something like $n$ steps (I say about because your approach isn't the simplest version of this type of attack; the simplest does take $n$ steps); ...
5
No matter how bad a protocol built on top of RSA is, there is no known risk that a private key leaks from valid plaintext/ciphertext pairs, even if the adversary chooses plaintext or ciphertext; that's one of RSA's virtues. Thus to the question is it possible with this information for Cindy to find $pri_A$ we can answer: as far as we know, no; and more, ...
Only top voted, non community-wiki answers of a minimum length are eligible
