# Tag Info

10

Ricky's link answers your main question in the comments (that knowing the private key is equivalent to knowing the factorization of $N$). But your "attack" is unfortunately part of a class of properties which might appear insightful at first, but which eventually boil down to something like this: "find integers $(m,k)$ such that $m+kn$ is a perfect square" ...

9

Actually, that was proposed here back in 1998 (sorry, an electronic version of the paper does not appear to be on the web) -- the author claimed a modest speedup in the private operations. However, that speed up would appear to be about the same if you just did "multiprime RSA", that is, selected an RSA modulus of the form $pqr$ for three distinct primes ...

9

The question asks how to systematically pick the public exponent $e$ in RSA. I'll stick to public modulus $N$ that is the product of exactly two distinct odd primes $p$ and $q$, but the choice of $e$ is not fundamentally different in multiprime RSA. What's an acceptable public exponent $e$? The public exponent in RSA should be an integer $e>1$ with ...

8

I don't think idea 1 can be made to work at all. The main point is that in order to generate a correct secret decryption key, the key generator must know the order of $\mathbb Z^*_n$, i.e., the totient of the modulus $n$. The generator knows that $n=p \cdot q$, where it believes that $p$ and $q$ are primes, and so it believes that the totient is ...

8

Rather than making an overly long question even longer, I post this as an answer. As part of the update process of the French security recommendations linked in the question, I suggested (June 2013) a waiver for the requirement/recommendation that $e>2^{16}$ when using a padding scheme with a security proof. It was kindly refused (within 6 weeks), with ...

8

We want a non-trivial factorization of a moderate odd integer $n$ into positive integers $p$ and $q$, knowing that such factorization with $|p-q|$ suitably small exists. Perhaps the most elementary method answering the question is trial division by integers starting at $\lfloor\sqrt n\rfloor$, going down. This succeeds after checking divisibility of $n$ by ...

8

I know an algorithm that runs in polynomial time would be able to break an RSA key pair "quickly". But how quickly is "quickly"? No way to say, it might be microseconds, and it might be large multiplies of the age of the universe. When we say that an algorithm runs in polynomial time, we're not saying anything about how fast the algorithm runs given ...

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

There's no real difference between $p$ and $q$ in RSA. It looks like OpenSSL just has the agreement "$p$ has to be bigger than $q$" for conveniences. One of the numbers has to be bigger than the other (otherwise they would be the same number, and $p = q$ is very bad in RSA). Just use two examples: $p = 13$ and $q = 11$. $p$ is bigger than $q$, all right. ...

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

A possible RSA variant uses: some odd exponent $e>2$ (that can be $e=3$ or $e=2^{16}+1$ as customary in standard RSA); $p$ and $q$ distinct large random primes, with $\gcd(e,p)=\gcd(e,p-1)=\gcd(e,q-1)=1$; $N=p^2\cdot q$; some $d$ computed such that $d\cdot e\equiv 1\pmod{\operatorname{lcm}(p,p-1,q-1)}$; public-key function $x\to x^e\bmod N$; private-key ...

6

This expands CodesInChaos's comment into an answer. Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and ...

6

No, the RSA key size is not the size of the private key exponent. It is customarily the number of bits in the public modulus (which is known as $N$). In other words, the key size is the integer $k$ such that $2^{k-1}\le N<2^k$. In most implementations (and all implementations conforming to PKCS#1), a private exponent $d$ has size in bits at most the key ...

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

To make it easier for humans to read.

6

Yes, what you have is enough to recover p in both cases. In the first case you just need to write the proper equation to be then solved thanks to Coppersmith method to find small roots of univariate polynomial. As explained by Alexander May in pages 40 and 41 of his thesis what you ask is always doable if the unknown bits are consecutive (and you have at ...

6

I don't know about computing things in parallel, so I will ignore that part of the question. First, please note that the encryption algorithm is rarely the the weak point of the security. It is far more likely that you will have problems with the implementation, some spyware installed on your computer, a weak password (If you use qwerty as your password, ...

6

This describes some attacks against textbook RSA (also known as raw RSA), where the public or private functions $x\to y=x^e\bmod N$ or $y\to x=y^d\bmod N$ are applied directly to the message. Encryption / Decryption Determinism in textbook RSA allows an attacker - given a ciphertext - to search for the corresponding plaintext. Determinism also leads to ...

6

No, RSA encryption and signature is performed in (the multiplicative semigroup of) the factor ring $\mathbb Z/n\mathbb Z$ which is not a field since the non-zero elements $kp+n\mathbb Z$ (for $0<k<q$) and $kq+n\mathbb Z$ (for $0<k<p$) do not have multiplicative inverses. (However, one easily observes that all other non-zero elements are ...

6

Very important: Determining whether an integer is prime is significantly easier than factoring it (at least in the current state of our knowledge). We can easily determine whether integers having thousands of decimal digits are prime, but such integers are far beyond the reach of current factoring algorithms. Now to answer your question: "plain" RSA does ...

5

You are showing "textbook" RSA, which is not used in practice. In practice RSA is defined within PKCS#1, defined in RFC 3447. The output is converted from a positive integer to an octet string (or byte array) using I2OSP. Note that RSA is almost never used to directly encrypt text or characters. Normally hybrid encryption is used. Whatever algorithm, scheme ...

5

You seem to have some misconception here. Obviously, you are investigating chosen ciphertext attacks (CCAs) on textbook RSA instead of chosen plaintext attacks (CPAs). To help you with your understanding I am discussing CPA on textbook RSA first. To analyse all these kinds of attacks we formally model the attack as a game between an adversary (trying to ...

5

Unless otherwise stated, $a$ is any integer representative of an eponymous element of $\mathbb{Z}_p$. \begin{align} a^3\equiv a\pmod p &\Longleftrightarrow a^3-a\equiv0\pmod p\\ &\Longleftrightarrow a\cdot(a^2-1)\equiv0\pmod p\\ &\Longleftrightarrow a\cdot(a-1)\cdot(a+1)\equiv0\pmod p\\ &\Longleftrightarrow\begin{cases} a\equiv0\pmod ...

5

Actually, one would be able to crack a $2n$-bit RSA public key in $O(\pi(2^{n+1})-1)$ time. However, $O(\pi(2^{n+1})-1) = O(2^n / n)$, and we already know how to factor $2n$-bit numbers faster than that. Hence, even if someone could come up with such a list (and find some place to store it), it wouldn't actually affect the security of RSA.

5

The attack is even more simple with RSA than with symmetric keys, because the asymmetric encryption key is assumed to be public. Let me tell you a story involving Alice, Bob and Mallory :). Alice wants to send a message to Bob using RSA. Alice encrypts the message using Bob's public key and sends it Mallory performs a Man-In-The-Middle attack, and ...

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

Here are some hints on how it's done on Mega: The password provided is passed through a KDF to derive a key, that is used to en-/decrypt the master key (later provided by the server through an API call). To bring it down to the crucial bits: The KDF applies $2^{16}$ rounds of AES-128 with it. The details can be found in the function prepare_key() of the ...

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