# Tag Info

10

This depends on the public-key system (algorithm). For RSA, technically the private and public key (i.e. the exponents, the keys share the same modulus) are symmetric, you can swap them, and it still works. But you usually don't want to do this: The public exponent is usually a small number (like $3$ or $2^{16} + 1$) in order to speed up ...

10

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 ...

7

Short answer No, RSA encryption with a private key is not the same as RSA signature generation. RSA encryption can only be performed with an RSA public key according to the RSA standard. The terms Raw RSA or textbook RSA are often used to indicate RSA without a padding scheme. Raw RSA simply consists of modular exponentiation. Raw RSA is vulnerable to many ...

7

Yes, you are correct. The simplest way without stepping outside NaCl would be to have both create an ephemeral, random crypto_box_keypair, then exchange public keys using their long term keys. Further communication would use that new keypair for crypto_box during that session. After they are done with the session, delete those ephemeral keys from memory. ...

7

If $p$ and $q$ are 1024-bit primes, then by definition of the bit size of an integer (at least, a prime in a cryptographic context with glimpses of RSA), $2^{1023}\le p<2^{1024}$ and $2^{1023}\le q<2^{1024}$. Thus their product $n=pq$ verifies $2^{2046}\le n<2^{2048}$, and $n$ is a 2047-bit or 2048-bit integer. We show by exhibition that both cases ...

7

You are looking for Proxy Re-Encryption. From a high-level viewpoint, a proxy re-encryption scheme is an asymmetric encryption scheme that permits a proxy to transform ciphertexts under Alice's public key into ciphertexts decryptable by Bob's secret key. In order to do this, the delegator $A$ gives a special re-encryption key $rk_{A \rightarrow B}$ to the ...

7

Copy / paste that key into http://phpseclib.sourceforge.net/x509/asn1parse.php and you'll see that there are several different integers in there. p is there, q is there as is the exponent and several other integers to speed things up by taking advantage of the Chinese Remainder Theorem. The key is encoded using DER and derives semantic meaning via ASN.1. ...

6

Think about this: what does it mean that $\gcd(e_B, e_C)=1$. Formally that means there exist some $s_1, s_2$ such that $e_Bs_1 + e_Cs_2=1$. Say you have two ciphertexts (the following math is all done modulo the shared modulus), $C_B=M^{e_B}$ and $C_C=M^{e_C}$. You can do the following: \begin{align} ... 6 So your protocol goes like this: Alice generates a key pair (a_{priv}, a_{pub}) and sends a_{pub} to Bob. Bob generates a key pair (b_{priv}, b_{pub}) and sends b_{pub} to Alice. Alice generates a message m and sends Enc(Sign(m, a_{priv}), b_{pub}) (or Sign(Enc(m, b_{pub}), a_{priv}), I'm not sure which of both is usually used by PGP) to Bob. ... 6 The only reason you are seeing this is because you are dealing with such small primes. With primes like we would use in practice (1024 bits), the probability of this happening is very, very small. And, it can only happen when e>\sqrt{\lambda(n)}. Since we typically use e=65537 in practice, it is guaranteed to not happen. Anyways, there is no mistake ... 5 How do we keep \phi(n) secret? We don't tell people what it is. The problem of finding \phi(n) given n is a hard problem (if n is hard to factor). So, if we give people a number that they can't factor, and we don't give them \phi(n), they can't determine it on their own. 5 The paper you link to in your comment is a fictional paper where the author (inspired by experiences with reviews he got for his own papers) imagines how negative reviews to groundbreaking papers could have looked like. So its just fun ;) AFAIK the RSA paper has never been rejected (but the very first paper of Ralph Merkle on public key crypto got rejected, ... 5 If you need security against quantum attacks, there aren't that many options. I would go for a lattice-based encryption like NTRU or something based on ring learning with errors. There are no "magic numbers" involved and the assumptions they are based on have been scrutinized by the academic community. NTRU has been around for a decade and has pretty good ... 5 Yes, you encrypt the file with a symmetric key, then encrypt that symmetric key with each of the recipients public keys. gpg can do this by adding multiple --recipient options. 5 This exists. It is called Broadcast Encryption http://en.wikipedia.org/wiki/Broadcast_encryption . Latest research even allows for Traitor tracing http://en.wikipedia.org/wiki/Traitor_tracing , meaning that even if two people give a part of their secret keys to form a "pirate decryptor", there is an algorithm which will find one of the users that colluded. ... 5 I wondered if there is a "simple" description of the set of numbers n that have this property. Yes, there is; n has a prime factorization p_1 \cdot p_2 \cdot ... \cdot p_n such that all the primes are unique (i.e. n is square-free), and for each prime factor p_i, p_i-1 must be a divisor of 24. In other words, each prime must be a member of ... 5 It is correct that the given private key does not encode a single integer, and that it includes two primes p and q. More precisely, that Base64 data encodes a string of bytes, which is an RSAPrivateKey encoded per ASN.1 DER-TLV (and thus BER-TLV) following PKCS#1v2 Appendix A.1.2 (likely restricted to version 0). It decodes to: 30 ASN.1 tag for ... 5 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 ... 5 Towards the security of the signature scheme, no precaution against timing attack is necessary when verifying an asymmetric signature. That's because there is no secret involved, thus no information leak to fear. However it can happen that the message, or the signature itself, is intended to be secret; a leak by timing dependency (during computation of the ... 4 When using a Discrete Logarithm based scheme, such as SRP, the rule of thumb is to always use private exponents with a bit length twice the desired security strength. Hence, a 128 bit exponent a will at most give you 64 bits of security. If you want 128 bit security, you need (at least) a 256 bit exponent. This is because the algebraic structure of the ... 4 It depends on what you mean by RSA. If you mean the plain textbook RSA where P = C^d \bmod n (decryption with private key d) and S = M^d \bmod n (signature generation), then yes, they are the same. However, textbook RSA is inherently unsafe, and for real-life RSA such as RSA-OAEP+ (encryption) or RSA-PSS (signatures) signing is not the same as ... 4 You've mostly pieced it out. This is a DER encoding the the public key, and consists of a sequence of two integers (the first being the modulus, and the second being the exponent). Here is the breakdown of the encoding: 30 The value 30 is used to signify 'sequence'; this is a container that carries a list of DER-encoded objects. 82 01 0a Whenever we ... 4 You got what a "semiprime" number is; it's a number which is the product of two primes. When people talk about "multi-prime RSA", what they mean is something which is pretty much the standard RSA algorithm; however the modulus is the product of at least 3 prime numbers (as opposed to standard RSA, which has only 2 prime factors). Why would anyone do this? ... 4 While the way that Robert showed can work if e is small (and if e \cdot d \equiv 1 \pmod{\phi(n)} (which is not necessarily true), there is a slightly more complicated method which will work in any case. What we do is compute \lambda = (e \cdot d - 1)/ 2^k odd (and k is the integer that makes \lambda odd. The special property that \lambda has ... 4 I give another simple proof using the leftover hash lemma. The proof goes as follows, where I'll abuse the notation and assume that q is prime. Game0 The adversary can see(A,b,c,u,v,w,s) = (A, As+e, At+f, rA, rb+x\lfloor q/2 \rceil, rc+y\lfloor q/2 \rceil, s).$$Game1 The view is changed as$$(A,b,c,u,v,w,s) = (A, As+e, c, rA, rb+x\lfloor q/2 \rceil, ...

4

xagawa's original answer is almost correct, except for the valid concern pointed out by Florian in the comments. (The updated answer looks good to me.) The answer to the question is "yes," except that the most 'lattice-y' proof works for the modified version of the Regev system defined in Applebaum-Cash-Peikert-Sahai CRYPTO'09. (A version of this was also ...

3

Originally we had restrictions like this in place as the alternative was emails about bugs in ciphers like RSA resulting from people not understanding the implications of modular arithmetic (if you are going to push right to the boundary you really have to understand what's going on). Having said that, I actually think we'd outgrown this by the time ElGamal ...

3

In standard ElGamal you compute the second component of the ciphertext as $m\cdot y^k \bmod p$ where $k$ is your randomness and $y$ your public key. Consequently you multiply two group elements in $Z_p^*$ and therefore $m$ needs to be an element of $Z_p^*$, i.e. $1 \leq m\leq p-1$. If you use exponential ElGamal, your message can come from $Z_{p-1}$, i.e. ...

3

ECDH or DH for that matter doesn't provide any authentication of a user. ECDSA as a public key scheme does provide authentication, but lacks validation. You need to certify that the exchanged public keys are indeed from Alice or Bob. So Alice and Bob must let an authority certify their own public keys such that Alice trusts the authority of Bob and Bob ...

3

As already mentioned in a previous comment, ECIES (a hybrid encryption scheme) is typically the way to go when implementing asymmetric encryption on elliptic curves, as it is standardized. It provides chosen ciphertext security (IND-CCA). But as you are looking for "pure" public key encryption schemes, here we go: ElGamal can not only be implemented in ...

Only top voted, non community-wiki answers of a minimum length are eligible