Tag Info

Hot answers tagged

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

Selecting a small $d$ is known to be insecure. Wiener has shown in 1990 that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the public key $(N,e)$. If you're interested in making the private computational cost cheaper, then I would suggest that RSA is not the best solution; I would recommend you start looking at ...


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

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

Rick Demer already wrote the answer in the very first comment, but without explanation: Hybrid encryption. But since you asked for a real practical example to encrypt your word document, this is how: Your file is on your disc, and it is 100,000 byte large. You can then do: First, you start up a random number generator. Preferably you should either have ...


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


6

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


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

Yes, we need symmetric cryptosystems, for many reasons; to give three of these: We need a hash function to make most asymmetric cryptosystems secure (e.g. we simply do not have a secure signature system based on RSA without a hash), and current hash functions are (or are built from) symmetric cryptosystems. All asymmetric encryption cryptosystems are bound ...


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

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


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

Yes, absolutely. Here is the standard construction to address this problem. Let $pk_1,\dots,pk_n$ be the public keys of the $n$ recipients. We pick a random symmetric key $k$, encrypt the message $m$ (using authenticated encryption) under key $k$ to get $c=AE_k(m)$, and then encrypt $k$ under each of the public keys. Finally, we form the whole ciphertext ...


4

Timelock puzzles solve this problem. For instance, consider the function $f(x) = x^{2^t} \bmod n$, where $n$ is a RSA modulus and $t$ is large. For people who don't know the factorization of $n$, computing $f$ takes $t$ squarings modulo $n$. If you do know the factorization of $n$ (the private key), then computing $f$ can be done with $O(\lg n)$ ...


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

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


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



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