Hot answers tagged

76

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


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

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


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

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


1

When you connect to a secure site the certificate validation happens. Certificate validation failure can happen when: Fields CN or SAN dont't match the site's domains. That means that the certificate was issued for a different domain. Invalid digital signature. Certificate has been altered. Unknown certificate issuer, thus unknown intermediate CA or root ...


1

In the standarized RSA algorithm the private key $d$ is calculated computing the modular multiplicative inverse with the Extended Euclidean GCD that satisfies: $1\equiv e \cdot d\pmod {\varphi(p \cdot q})$ Notice that modular multiplicative inverse can be expressed as: $$d=\frac{\varphi(p\cdot q)\cdot k + 1}{e}$$ for some $k$ multiple of ...


1

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


1

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


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



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