# Tag Info

78

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

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

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

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

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

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

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

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

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

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

3

Suppose you want to obtain the signature $s = m^d \bmod n$ on a chosen message $m$. Here is that attack. You ask the signer to sign a random message $m_1$ and obtain the corresponding signature $s_1 = m_1^d \bmod n$; You compute message $m_2 := m\cdot m_1^{-1} \bmod n$ and ask the signer to sign message $m_2$; you obtain the signature $s_2 = m_2^d \bmod ... 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 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 ... 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 The Procedure Step 1: Factor the original signature$s$into$s=\prod_{i=1}^n s_i$and then exponentiate each signature with$e$as in:$m=\prod_{i=1}^n s_i^e=\prod_{i=1}^n m_i$. Different methods to obtain multiple$s_i,m_i$pairs work just as well, such as asking the signing oracle. Step 2: Build a new message with a valid signature as the product of any ... 2 Let$n = pq$. By assumption,$3$divides$\varphi(n) = (p-1)(q-1)$. Without loss of generality, I assume that$3$divides$(p-1)$or, equivalently, that$p \equiv 1 \pmod {3}$. Fact Let$p$be a prime such that$p \equiv 1 \pmod 3$. Let also$c$be a cubic residue modulo$p$. If$y$is a cubic root of$c$then so are$y\cdot \omega \pmod p$and$y \cdot ...

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

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