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


9

This is a common mistake, so I'd like to give an in-depth answer. Basically, what you are proposing is to rely on the ONE-WAYNESS of RSA as a ONE-WAY FUNCTION, rather than relying on its CPA or CCA security as an encryption scheme. The advantage of using RSA as a one-way function is that no padding etc is needed. Now, the first important thing to note is ...


8

Definitions In RSA, an encryption key is a pair of integers $(N,e)$ with $N$ the product of $m\ge2$ distinct odds secret primes $r_i$ (with $0<i\le m$), and $e$ is such that $\gcd(e,\lambda(N))=1$ where $\lambda(N)=\operatorname{lcm}(r_1-1,\dots,r_m-1)$ is the Charmichael function. It follows that $e$ is odd. Typically, other conditions are added, like ...


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

The real question isn't "Why doesn't Suite B use P-521?" It is, "Why doesn't Suite B use AES-192?" NSA were only interested in 192-bit security for Suite B, but they chose to use AES-256 because AES-192 wasn't widely supported. "In fact we had wanted to use AES -128 and AES-192, but a quick survey of AES implementations (hardware centric, I believe) ...


6

In the basic fixed window method of performing point multiplication, we compute the value $nP$ (where $n$ is the integer we're multiplying by, and $P$ is the basis point) by finding the base $b$ representation $n = d_k b^k + d_{k-1} b^{k-1} + ... + d_1 b^1 + d_0 b^0$ (where $0 \le d_i < b$), and then computing first $1P, 2P, ..., (b-1)P$ and then $nP = ...


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

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

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


5

To generate your pair of keys with elliptic curves first you have to chose your domain parameters (I think this name may comes from the P1363 naming convention, or perhaps it's previous). Those domain parameters will be public. For example for curves over finite fields those parameters are: ${p,a,b,G,n,h}$. The lower level operations will be made in ...


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

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


4

I think that there is no chance of getting such an asymmetric cipher simply because you forgot about science. The security on todays asymmetric cryptography is mostly based on the assumption that some mathematical algorithms cannot be reversed (e.g. the discrete logarithm or integer factorization). If mathematics solves this problems then the algorithm is ...


4

If $p$ is prime, then $\phi(p) = p-1$; so the question is "given $k(p-1)$, can someone get a good guess of what $p$ might be?" It is unlikely that the attacker would be able to limit it to one particular value of $p$ (as there are likely to be multiple values of $p$ that are plausible), however the attacker might be able to construct a short list of ...


4

You are essentially asserting that if $k \equiv 1 \pmod N$, then $a^k \equiv a \pmod N$. This is false in general. The correct assertion is the following: $a^k \equiv a^\ell \pmod N$ if $k\equiv \ell \pmod{\phi(N)}$. In more general group-theoretic terms, if $a$ is an element of order $n$ in a group $G$, then $a^k = a^\ell$ if and only if $k \equiv \ell ...


4

The only security issues that I can think of when sharing the same key among several users (in an asymmetric encryption system used to broadcast messages) are: We can't revoke a single user without impacting all the others. We loose the flexibility to encipher to an arbitrary set of users (which, for large messages and when using hybrid encryption, has ...


4

Writing this as a serpate answer, but it goes along fgrieu's one Key management, and specifically storing keys securely, is one of the harder tasks in the security field. By the principle "security is as strong as the weakest link", handing out private keys to multiple parties is a bad idea - an attacker wins as soon as he corrupts the most insecure device. ...


4

The original poster clarified that: the application of RSA is signature (not encryption as originally stated); at least one signature $s$, the value of $N$, and $e=3$ are given; the signature is by signing an MD5 hash of a message, and a hash of the message matching the signature $s$ is also a given. The first, low-effort thing to do with the givens is ...



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