# Tag Info

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

0

I naively forgot that with a "random" amount of padding added the receiver would not know how many bytes to remove. That is why PKCS #5/#7 add the number of bytes as the padding value. For example, if we need to add 4 bytes then the last part of the message would look like: [... 04 04 04 04]. So the answer is PKCS #7 is the only possible way to add padding ...

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

-1

$e$ and $d$ cannot both be small, because $ed$ must equal at least $(p-1)(q-1)+1$, which is very large if the scheme is to provide any security against factoring algorithms.

0

Let $e\ne 1,-1$ be the public exponent such that $e^2=1 \pmod {\phi(N)}$, so we have: $$(e-1)\cdot (e+1)=0 \pmod {\phi(N)}$$ then we can compute $\phi(N)$ and factor $N$.

4

1) To choose $e$, this value have to be between $1$ and $phi=(p-1)(q-1)$, with $mdc(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 ...

0

Yes, math behind this work. But it seems that you are asking, can both public and private exponent be the same value? Answer is no, because you jeopardize the whole system. By choosing equal exponents, you create two identical keys. And if some eavesdropper steals public key, he can decrypt message.

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

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

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

0

For completeness, here is how to compute $d$ without resorting to the value of public exponent $e$. Compute $\delta = \gcd(p-1,q-1)$; Define $p' = p-1$ and $q' = (q-1)/\delta$; Compute $i_{q'} = (q')^{-1} \bmod p'$ and $d_{q'} = d_q \bmod q'$; Return $d = d_{q'} + q'[i_{q'} (d_{p}-d_{q'}) \bmod p']$. Note that the so-obtained value for $d$ is defined ...

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

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

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

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

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

0

Some things I have done that I thought were fun and enjoyable learning experiences: Make an encrypted virtual file system Requires (password based) key management, symmetric encryption, hashing, database queries Encrypt data on writing to the db, decrypt on reading Support multiple algorithms: AES, Camellia, sha256, sha3, etc Support multiple modes ...

0

There are a lot of useful tools out there in many programming languages. Java is a great example of one with lots of resources (see here) Why don't you have a go at implementing a file encryption system, whereby you generate keys and encrypt/decrypt data. This can assess many things such as your understanding of cryptography, programming, and key ...

0

Window size(w) depends on the NIST curve and the algorithm that you are going to use for point multiplication. I suggest you to look to the paper from Brown et al. Software Implementation of the NIST Elliptic Curves Over Prime Fields. They provide the number of operations in algorithms w. r. t. changing window size for some point multiplication algorithms. ...

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

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

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

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

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

0

So this feels like a homework question, as such I"m not going to give you the full answer, but yes, yes you can. https://en.wikipedia.org/wiki/Homomorphic_encryption#Unpadded_RSA Is the best starting point I can give without giving away the barn, but essentially rsa is homomorphic, and you can exploit that and repeated calls to the oracle to do what you ...

1

(a) $\mathbb{Z}_8^* = \{1,3,5,7\}$. (b) $x = 3$. (c) Assuming $a \in \mathbb{Z}^*_{15}$: $a^8 \bmod 15 = 1$ and $a^9 \bmod 15 = a$. (d) $M = 4$.

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

1

Factoring $\varphi(n) = 22200$, we get $22200 = 2^3 \cdot 3 \cdot 5^2 \cdot 37$. The condition $d = e$ implies $e^2 \equiv 1 \pmod{\varphi(n)}$. In turn, this yields $e \equiv \{\pm 1,\pm 3\} \pmod{2^3}$, $e \equiv \pm 1 \pmod{3}$, $e \equiv \pm 1 \pmod{5^2}$, and $e \equiv \pm 1 \pmod {37}$. All possible solutions are then obtained through Chinese ...

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

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

1

In this RSA setting, I am assuming encryption key is $e$ and decryption key is $d$. Relationship between encryption and decryption keys is that decryption key should be multiplicative inverse of encryption key in modulo $\phi(n)$ i.e. $$d=e^{-1} \mod \phi (n)$$ So that, $$de≡1 \mod \phi(n)$$ So, our goal is to find out $e$ and we can find out this as ...

1

Consider two numbers $a$ and $b$ that square to the same value modulo $n$ and don't just differ by the sign. $$a^2 \equiv b^2 \pmod n2$$ $$(a-b)(a+b) \equiv 0 \pmod n$$ Neither of the factors on the left is 0 (or equivalently a multiple of $n$), thus each of them must contain one of the prime factors of $n$. Thus you can use $\operatorname{GCD}(a-b, n)$ ...

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

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

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

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

0

$(e*d) \text{ mod } (\phi(n))=1$ $(17*d) \text{ mod } 6000022000020=1$ $d=4235309647073$. I used WolframAlpha to compute d.

0

Can you please describe your functional requirements in more detail, i.e. what are you trying to solve? That will ensure that you get most appropriate advice. What do you care to achieve? server to authenticate the client making the reservation? a way for the client to send its driver license in a confidential manner? client to authenticate the server ...

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

3

For private key operations you need at least $n$ (the modulus) and $d$ (the private exponent). The primes $p$ and $q$ let you calculate those – or use some shortcuts for quicker computation – so they also suffice. In practice RSA keys often include all of those values, to avoid having to compute them as needed and to allow for optimized and unoptimized ...

8

Assumption: $e$ and $d$ are prime with $N$. If we use the multiplication instead of the power. We have $d \equiv e^{-1} \pmod N$ : \begin{align}c \times d &= m &\mod N\\ m \times e \times d &= m &\mod N\\ e \times d &= 1 &\mod N \end{align} (It has to work for any $m$ so we can suppose $m$ prime). $e$ and $N$ are publicly known, to ...

16

Suppose an RSA public key is still $(e, N)$ and the private key is still $d$. We have $Enc = (m*e) \text{ mod } N$ and $Dec = (c*d) \text{ mod } N$. The correctness of the scheme depends on the fact that $Dec(Enc(m)) = (m*e*d) \text{ mod } N = m \text{ mod } N$. This implies $e*d = 1 \text{ mod } N$. It is thus trivial to compute the private key given only ...

6

No, it is not easy! RSA is based on the difficulty of factoring the product $n=pq$ of two large prime numbers. But if you know $\varphi(n)$ for plain RSA you can compute the secret exponent $d=e^{-1}\bmod \varphi(n);\;$ and you can factor $n$ from the two equations $n=pq,\;\varphi(n)=(p-1)(q-1)$.

Top 50 recent answers are included