# Tag Info

## Hot answers tagged rsa

63

An ASN.1-encoded SSH private key contains the following integers in order: The public modulus $n$ and exponent $e$; The private exponent $d$; The prime factors $p$ and $q$ of $n$; The "reduced" private exponents $d_p=d\bmod(p-1)$ and $d_q=d\bmod(q-1)$; The "CRT coefficient" $q_{\text{inv}}=q^{-1}\bmod p$. The observation that the value of $d$ in such a ...

37

Surprisingly, very basic algorithms which the children learn at the basic schools are used. For instance: http://www.wikihow.com/Do-Long-Multiplication You can find a similar algorithm for sum, sub and division. Try to ask google for: "division on paper" The "power of" is little tricky. In cryptography you don't really need the "real power of". Instead ...

32

The answer is in the source, file sshrsag.c, line 9: #define RSA_EXPONENT 37 /* we like this prime */ This value $e=37$ matches the conditions for a reasonable fixed RSA public exponent: $e$ is odd, $e$ is at least $3$, $e$ is reasonably small. The later condition is good for speed of operations involving the public key (encryption, ...

28

There are two reasons by which such "huge" numbers can be computed in reasonable time. The first one is that we do not raise one integer x to some big exponent d. What we do is that we compute x raised to power d modulo an integer n. The modulo means that we are not interested in the final integer xd but only in the remainder of the Euclidian division of xd ...

19

Actually, if you're willing to consider a somewhat larger $e$, I found a solution that makes the decryption part real cheap. This solution has $e = 446185741$ and $n = ... 18 A couple things: This article is two years old, so take its predictions with a grain of salt. In the two years that have elapsed, the predicted advances have not materialized, and there is little indication they will soon. The core of those arguments was Joux's 2013 result on the discrete logarithm problem in finite fields of small characteristic. Those ... 17 The premise "we don't have a way of generating and verifying a 2048-bit prime number with 100% accuracy" is wrong (if we trust the computers performing the operations): it has long been known practicable ways to generate randomly-seeded provable primes, and it is a (somewhat marginal) practice in RSA key generation (see FIPS 186-4 appendix B.3.2). We can ... 17 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 ... 15 If we want to compact an existing RSA private key expressed as$(N,e,d,p,q,d_p,d_q,q_\text{inv})$, we can reduce it to$(e,p,q)$and easily recompute the rest as:$\begin{align} N&=p\cdot q\\ d&=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;\text{ or }\;d=e^{-1}\bmod((p-1)\cdot(q-1))\\ d_p&=d\bmod(p-1)\;\text{ or equivalently }\;d_p=e^{-1}\bmod(p-1)\\ ...

15

This question has many problems in the way it was asked, and clearly did not come after doing some investigation. However, since this seems to be a misconception that is spreading widely, I will relate to it. It is not true that the "crypto community" (whoever that is) believes that the NSA can break RSA. In fact, if Snowden taught us anything, it is that ...

14

Any $e$ such that $\gcd(e, (p-1)(q-1)) = 1$ will do. There is no need for it to be in the set $\{3,17,65537\}$; these last numbers are chosen for speed of encryption, mostly (two set bits leads to faster computation of modular exponentation), and these numbers happen to be prime, so the condiiton is easily checked. One often encounters other $e$, but many ...

12

You can use a seed to start a PRNG. Then you can use that PRNG to generate the two (or more) primes required to generate the key pair. Now if you save that seed you can regenerate the key pair, which means you don't have the store the modulus, CRT components or private exponent. So yes, it is possible to reduce the size, but this approach does have ...

12

Actually, if the RSA key generation is malicious, there are even more subtle ways that can someone can leak the key. The cleverest way I've seen works like this (assuming that we're generating an RSA-1024 key; for RSA-2048, we just use a larger curve): The attacker generates an EC public/private key pair; using a 192 bit curve for RSA-1024 is good. He ...

10

Why can the public key exponent not be negative? Technically, it can be. There's just no point to using such negative exponents in general, since for every valid negative RSA exponent, there is an equivalent positive one that is easier to calculate with. Specifically, for any exponent $e$, message $m$ and modulus $n = pq$, changing $e$ by any integer ...

9

An option strictly matching the question's statement (which requires $e=65537$) is to choose the public modulus $n$ as the product of many small primes $p_i$, perhaps $k=64$ primes of $32$ bits. That's multiprime RSA pushed to the max. The potential speedup is considerable. For small $k$, and standard arithmetic (quadratic multiplication and modular ...

9

Yes you can use Big-O notation to express runtime, that's customary. Formally, that does not give an upper bound on runtime for any fixed parameters, much less a lower bound; formally, that gives you an indication of how an upper bound would behave when some parameter grows to infinity, and no practical indication. However, in practice, when dealing with ...

9

Hash functions must be public, so if you want use RSA as hash function you should fix $K$. Now let $n$ be the RSA module and $H$ denote RSA hash function. We have $$H(M)=H(M+n)$$ so this function is not second preimage and collision resistant. Also this system is not first preimage resistant (with known public and private key): Let $M^k=h \pmod n$ ...

8

The use of the AES key many times is not a problem. However, there is a fundamental flaw with your solution. The server has no way of validating that it received the client's authentic public key. In particular, a man-in-the-middle can capture the client's public key, can forward its own public key to the server, and can then decrypt all traffic sent by each ...

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

8

You are looking at the ASN.1 encoding of private (and public) keys; the 00 values you see are an artifact of how ASN.1 encodes integers. ASN.1 is a method for describing data structures, and has ways to represents all sorts of data types. It wasn't designed with public keys (or cryptography) in mind; it was intended for more general use, initially ...

8

If your calculator is able to compute $n^2$, you can compute $m^e \bmod n$ using the binary exponential method. In this method, you should first compute the binary form of $e$. Let $\ell$ be the number of bits in $e$, and let $e_i$ denote the $i$-th bit of $e$, so that $e=\sum\limits_{i=0}^\ell e_i \cdot 2^i$. Now, with the algorithm below, you can compute ...

8

There is likely an assumption on the sizes of $p$ and $q$ that you haven't listed in your question that exists in the description. For example, Boneh's description of Wiener's attack has that $q<p<2q$. With that assumption, we can prove the inequality. We know that $$p+q < 2q+q$$ $$p+q < 3q$$ Furthermore, since $N=pq$ and $p>q$, we have ...

7

Mathematically speaking, there is no upper bound on the private exponent in RSA: assuming $d$ is a valid private exponent, then the valid exponents are the set of $d'=d+k\cdot\lambda(p\cdot q)$ with $k\in\mathbb Z$, where $\lambda(p\cdot q)=\operatorname{lcm}(p-1,q-1)$ since $p$ and $q$ are distinct primes; this set is unbounded. If you compute $d$ as an ...

7

If $d$ is a valid RSA decryption exponent, then so is $d \pm k \lambda(pq)$ for any integer $k$. As a corollary, we may always choose the decryption exponent to lie in the range $0 < d < \lambda(pq)$. In fact, there's generally no reason to choose the decryption outside that range: a larger exponent would just make decryption slower, while using a ...

7

I do not believe that there is any reasonably efficient way to reconstruct the lsbits; if there were, then a good fraction of the RSA keys out there could be efficiently factored (!). Here's why: a lot of RSA keys have a modulus $n = pq$, where $p$ and $q$ are primes of equal size. Then, let us assume a small $e$ (it needs to be relatively prime to $p-1$ ...

7

Loosely define the RSA problem as solving for $x$ the equation $c=x^e\bmod N$, with $x$ random in $\{0,1,\dots,N-1\}$ (or equivalently $c$ random in this set), and $(N,e)$ properly chosen. The best method we know for tackling that problem is factoring $N$, but we have no proof that there is no substantially better method. We do not know if the RSA problem ...

6

The archetypal algorithms that could take advantage of $p$ being close to the square root of $N=pq$ is Fermat's factorization method; and some improvements thereof. The basic Fermat factoring method makes about $(p+q)/2-\sqrt N$ steps. Applied to $N\approx 2^{127}$ and $p/\sqrt N\approx 0.98$ (as in the question) this is over $2^{51}$ steps. We have ...

6

No, you generally cannot swap the public and private keys. Your public key consists of a public exponent and a modulus. The modulus should be known to the person doing the encryption. The public exponent - in general - is a relatively small prime such as 3 or 65537 (Fourth number of Fermat). So given the modulus all an attacker has to do is guess the public ...

6

Yes, there are a few reasons to prefer ECDH over RSA: ECDH will perform much better; ECDH can provide forward security when used with ephemeral key pairs without a large performance overhead for creating those key pairs; ECDH should be impervious to most oracle attacks, i.e. timing based padding oracle attacks on OAEP. For the forward secrecy you require ...

6

As pointed by CodesInChaos, you'll need to know the padding used; depending on application that could be RSASSA-PKCS1-V1_5, or RSASSA-PSS, or some of the three schemes of ISO/IEC 9796-2, etc.. Hashing, and padding check, are a significant part of the code. In any case, yes, it is possible to implement RSA-2048 signature verification on a Cortex-M0 ...

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