# Tag Info

74

It (or rather, the software running on it) will use arbitrary-precision ("bignum") arithmetic. The way this works is basically the same way in which you (probably) learned to do arithmetic on paper at school. The arithmetic taught to us humans at school is base-10 arithmetic — that is, we represent numbers as strings made up of ten different digits, ...

15

However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms. Not categorically. Factoring a large integer is trivial if it is only composed of small factors. A fairly naive algorithm for factoring N is the following: while N > 1: for p in increasing_primes: while p divides N: N = N / p ...

14

The main reasons we usually choose $p$ an $q$ prime numbers are: For a given size of $N=pq$, that makes $N$ harder to factor, hence RSA safer. Although efficient factoring algorithms do not find factors by trial division, it remains much easier to find very small prime factors than large ones. If we chose $p$ and/or $q$ at random without consideration for ...

11

RSA moduli are generally of the form $N = pq$ for two primes $p$ and $q$. It is also important that $p$ and $q$ have (roughly) the same size. The main reason is that the security of RSA is related to the factoring problem. The most difficult numbers to factor are numbers that are the product of two primes of similar size. Note. There are basically two ...

7

Of course the processor cannot process such large numbers directly; this is done though a library such as GMP. See Wikipedia for a list of such libraries, and a good textbook such as that of Gerhard and von zur Gathen for the underlying ideas. The freely available Handbook of Applied Cryptography also talks about this, especially in Chapter 14.

6

$\varphi(n)$ is a multiplicative function: it is computed by the formula $$\varphi(n) = n \prod_{p \mid n} \frac{p-1}{p}$$ or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small. Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you ...

6

Is there a RSA scheme which produces fixed size signatures? Normally RSA signatures are fixed size. Depending on encoding and the details included, the length may vary by at least a few bytes, though. There is usually a known maximum at least. The last block can be as small as 1 byte. Is there any cryptographical risk doing this? No. ...

5

If you choose $p$ and $q$ at random of the same length, then they will be far away from each other with extraordinarily high probability. Thus, this is not an issue. In the past, there were those that recommend safe primes to make sure that neither $p-1$ nor $q-1$ would have all small factors. However, this isn't necessary (and is now not even recommended). ...

5

How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer? Like the answer you linked to shows, about $\log(N^2) = 2 \log(N)$. So 4096 for 2048-bit RSA, double that for 4096-bit. This paper (pdf) has an algorithm using $2n+3$ qubits, where $n=\log N$. How many qubits are required to break ...

4

There are four different solutions, of which three have been identified as the "trivial solutions" in the comments to this question. $e=d=1$ which is obviously fullfilling the condition that $1\cdot 1\equiv 1 \pmod{\varphi(n)}$ should hold. $e=d=\varphi(n)-1$ which is fullfilling the condition that $(\varphi(n)-1)^2\equiv 1 \pmod{\varphi(n)}$ as ...

4

The quoted recommendation is generally considered obsolete in the context of RSA with secure parameters, and is either disregarded, or replaced by asking that $\left|p–q\right|>2^{(n/2)–100}$ where $n$ is the number of binary digits for $N=pq$. This modern rule was in ANSI X9.31 (1998), and is still in FIPS 186-4 (2013), appendix B.3, criteria ...

4

If RSA 3072 is equal to 128 bit symmetric and 2048 is equal to 112 bit symmetric... To be precise, a 2048 bit composite is estimated to take approximately $2^{112}$ operations using the Number Field Sieve algorithm; 3072 bit composites are estimated to take approximately $2^{128}$ operations using that same operation. Since the Number Field Sieve (NFS) ...

4

1) To choose $e$, this value have to be between $1$ and $\phi=(p-1)(q-1)$, with $\gcd(\phi, e) = 1$, right? No; $e$ can be any value that's relatively prime to both $p-1$ and $q-1$ (or equivalently, relatively prime to $\operatorname{lcm}(p-1, q-1)$). There may be little point in choosing an $e$ larger than $n$; however there's no specific reason it ...

4

As others have noted, you typically use some sort of arbitrary precision integer library. I feel obliged to point out, however, that extending multiplication to large integers is decidedly non-trivial compared to addition. With addition, you have a single bit of carry from one word to the next, and on a typical processor you even have an instruction ...

3

To clarify scope: FIPS 140-2 itself doesn't say anything about DSS, though it has 186-2 as a reference. It was published in 2001, before 186-3 and -4, and has not been superseded. After 140-3 spent 8 years in draft they recently decided to consider using ISO/IEC 19790 instead! 140-2 Annex A (Approved functions) is updated frequently and does now reference ...

3

The paper is rather sloppily written, however it can be changed into the correct statement. The statement in the paper is: She takes randomly elements $f \in F^*_p$ and checks whether or not $f^{2x}=1$. With probability at least $1 − 1/\ell$ she finds $f$ of order $\ell$. As written, that's wrong. However, if we modify it to: She takes a random ...

3

Q: RSA 3072 is 65,536 more difficult to factor than 2048? If RSA 3072 is equal to 128 bit symmetric and 2048 is equal to 112 bit symmetric then 128-112= 16 and 2^16= 65,536. Basically yes. Q: In that case wouldn't this make 3072 more future proof against quantum computers or does Shor's algorithm mean they will both be equally useless? The point ...

3

This is not an answer; rather, I attempt to improve the method outlined in the question. Problem statement (slightly simplified): it is given an RSA public key $(N,e)$ with $2^{n-1}<N<2^n$, $n=2048$, $e=41$, a hash function $H=\operatorname{SHA-1}$ with output of $w=160$ bits. It is asked an $(m,s)$ with $0\le s<N$ and $H(m)=(s^e\bmod N)\bmod2^w$. ...

3

Our goal is to find a root $(x_0,y_0)$ in $\mathbb{Z}_e$ of the polynomial $f(x,y) = x(A+y)-1$. Finding roots of a polynomial in any $\mathbb{Z}_n$ isn't an easy job, in order to solve the problem Coppersmith had the idea to reduce to problem to finding a root $(x_0,y_0)$ over $\mathbb{Q}$ of some other polynomial $f'$ related to $f$. About Coppersmith ...

3

While other answers approach the problem from the simpler question, "How do computer handle large number computation" the specific question is how computers handle large modulus numbers, and the answer is that there are algorithms and techniques specifically for handling large modulus calculations. Wikipedia provides a short list of terms and algorithms one ...

2

Your $d$ is indeed incorrect. I get $d = 4235309647073$, using Wolfram alpha. As to python, use the builtin pow function with a third argument equal to the modulus. So message = 6 encmessage = pow(message, 17, 6000029000033) assert message == pow(encmessage, 4235309647073, 6000029000033) which will apply a smart algorithm like those in answers to this ...

2

Is there any possibility to make a successful verification with just modifying message and signature, and without modifying public-key ? One would certainly hope not. If you can, then you've just shown that the signature algorithm used is broken, and not to be trusted. For a signature method to be considered secure, then it is required that someone ...

2

I wanted to help break down exactly what you're seeing. If you take your base64 string: MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB You then decode it into hex: 30 81 9F 30 0D 06 ...

2

Edit: My brain misfired and my original answer was based on an incorrect assumption. I blame this on a case of the Mondays. RSA-OAEP Recall that RSA-OAEP is defined as follows (with $m$ being the message to encrypt, $G$ and $H$ being random oracles and $(e, N)$ being a standard RSA public key): $Encode$: Select a random $k$-bit integer $r$. Pad out $m$ ...

2

To basically summarize Ricky Demer's answer, regardless of how "random-looking" your private key is, an attacker can always recognize the correct private key as long as they have access to at least one of the following: the public key, both the ciphertext and the plaintext of a message encrypted using the public key, or even only the ciphertext, as long as ...

2

Usually choosing a safe password and standard parameter for the PBKDF2 key derivation would be enough protect your cipher. If PBKDF2 is correctly used, the symmetric key you get as output is well generated and attacking the ciphertext is infeasible. Protecting a private key as you're doing is a standard operation, usually the password is used (in PBKDF2) to ...

1

The padding used for RSA is not the PKCS #5/#7 padding (as you seem to suggest in your own answer), but the Wikipedia entry seems to refer to PKCS #1 v1.5 (RFC2313)) which uses a padding 00 || BT || PS || 00 || D where for RSA encryption we start with a 0x00-byte (to guarantee that the resulting number is below the modulus), then use BT (Block Type) equal ...

1

I'll start with a point corresponding to ddddavidee's edit: ​ If there exists a PKE scheme, then there exists one for which private keys can trivially be distinguished from randomness. Just modify the key generation algorithm to append so that the new private keys end with length(original_private_key) zeros, and modify the decryption algorithm to ignore ...

1

First things first: Don't roll your own crypto. As for your current approach: This is basically a vigenere cipher which is inherently broken, provides not integrity protection and wouldn't even encrypt known / predictable bit positions (where the ASCII code is constant zero or one). As for an improved version: Use a well-known encryption algorithm (e.g. ...

1

In your case you can factor $N (= 85)$ and use that to compute $\phi(N)$, which in turn allows you to compute $d = e^{-1} = 19^{-1} \text{ mod } \phi(N)$. Factoring $N$ yields $5 * 17 = 85$ which in turn means $\phi(N) = (5-1)(17-1) = 64$. Finally, $d = 27 = 19^{-1} \text{ mod } 64$. Note that for most actual instances of RSA $N$ is usually at least 1024 ...

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