Hot answers tagged

18

This question can be summarized: the attacker found a $d$ that did not satisfy $e \cdot d \equiv 1 \pmod{ \phi(n) }$, but it works; what's going on. It turns out that $e \cdot d \equiv 1 \pmod{ \phi(n) }$ is not necessary (it is sufficient). The necessary and sufficient conditions are: $$e \cdot d \equiv 1 \pmod{p-1}$$ $$e \cdot d \equiv 1 \pmod{q-1}$$ If ...


10

RSA private key can be found in two ways with $n = p\cdot q$, $p = 11$ and $q = 13$ if Euler's totient function is used as in RSA paper: $$\varphi(n)= (p-1)(q-1) = 120$$ is used then $d = 67 = e^{-1} \bmod 120$ If Carmichael Function used as requried in FIPS 180.4and allowed in PKCS#1 v2.2 standards: $$\lambda(n) = \text{LCM}(p-1,q-1) = 60$$ is used ...


8

Let $n = p \cdot q $ be product of distinct primes $p$ and $q$, of arbitrary size as in the RSA setup. The RSA public key $(n,e)$ contains both the modulus and the public exponent, so we assume both are known. Let $b = p +q$. If $b$ is also known, then we can form a quadratic equation as $$ f(x) = x^2 - b x + n \label{1}\tag{1}$$ by using the following ...


5

Practically, when RSA is used to encrypt strings, what is the $x$ in $x^e\bmod n$? That depends on the variant of RSA. Among the most common: Toy-sized textbook RSA, where the public modulus $n$ is small: it is customary to encrypt letter by letter (or pair of letters, as in the original RSA article's small example) and concatenate the RSA cryptograms. ...


5

If we're using the cyphersuite TLS_AES_128_GCM_SHA256; and GCM is using Encrypt-then-MAC (which appears to be always?) and is configured to use a 128-bit tag; and AES_128 is encrypting plaintext in blocks of 128 bits; then is GCM adding a 128-bit tag onto each one of those blocks (thus, halving the amount of cyphertext that can ultimately fit into the data ...


4

Is there a way how Alice can proof to Bob that she is in possession of the private key? Here is one possible way: Bob selects a random 2048 bit value $m < n$ and computes $m^e \bmod n$ and sends that and $\text{SHA3_256}(m )$ to Alice. Alice, with the private key, recovers $m$, and verifies that $\text{SHA3_256}(m)$ matches the value she received from ...


3

Note that this isn't really a cryptography question; it's about how various kinds of data representations work. The data in this case happens to be cryptographic, but the same or similar methods, operations, and issues can occur with any kind of data. In this link, it says ed25519 has a length of 64 characters Is this base64 encoded characters? And does ...


3

But how can we say there's a absolute collision in these two lists? Well, we know that $c^d \equiv m$ for some value $d < n$, because of this, we have $d = Nk + j$ for some pair of integers $0 \le j < N$ and $0 \le k < N$. We see that $c^j$ will appear somewhere in the first list, and $m \cdot c^{-Nk}$ will appear somewhere in the second list. ...


3

Firstly, I am not sure about how I should narrow down the topic. It is better to ask your advisor to help you for selecting a good research topic. Secondly, which prerequisite knowledge do I need? Also, do you suggest any foundational books on the topic? A roadmap for learning Elliptic Curve Cryptography: Beginner: you can learn the basic of ECC by ...


2

Based on your comments I have a feeling that may be you don't really understand what a huge number of combinations a 256-bit key means. At the first glance 256 bit is "just" 16 bytes. But look at it closer. With 256 bits we can encode $2^{256} = 10^{77}$ numbers. It is 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 ...


2

I want to show that a malicious sender (Alice) can attack this protocol if it can deviate from it, namely, send a wrong RSA key pair, and learn the secret bit $b$. You can, in fact, show this (or, rather, the OT would require a ZK proof by Alice that $\gcd(e, \phi(N)) = 1$) However, I don't exactly understand how sending such an invalid input $e$ helps. ...


1

As per section 9 of the paper, the encoding used is required for the security of the scheme. The encoding operation may introduce some randomness, so that different applications of the encoding operation to the same message will produce different encoded messages, which has benefits for provable security. For such an encoding method, both an encoding and a ...


1

As @fgrieu said, it will work when ${|p-q|< N^{1/4}}$ , where ${\sqrt N}$ and ${A}$ both are very nearer. then we can take ${A = \sqrt N}$ to start with. Let ${A=(p+q)/2}$ , i.e., A is mid point of p and q, which could be nearer to ${\sqrt N}$ There exist an integer ${x}$ so that, ${A-x=p}$ and ${A+x=q}$ ${N=pq}$ ${=}$ ${(A-x)(A+x)=A^2-x^2}$ ${x= \...


1

I am assuming you meant to use a=2, so that if it sends an error message, we know that MCB was 1. Anyway RSA in practice is never used in raw form like this precisely because this malleability allows attacks like you just mentioned. Such malleability also allows an attacker to create fake signatures from an oracle and with good padding, we cannot trick any ...


1

The proposed system is close to the safe RSA-KEM, with some exceptions: The condition $\gcd(P-1,e)=1$ and $\gcd(Q-1,e)=1$ is missing. This must be checked when generating $P$ and $Q$. In the case of prime $e$ (as in the question) this simplifies to $P\bmod e\ne1$ and $Q\bmod e\ne1$. The random key is 512‑bit, when in RSA-KEM it is typically drawn in $[0,P\,...


1

According to RFC 2437... RSAES-OAEP can operate on messages of length up to $k-2-2\cdot hLen$ octets, where $hLen$ is the length of the hash function output for EME-OAEP and $k$ is the length in octets of the recipient's RSA modulus. The padding string $\text{PS}$ in EME-PKCS1-v1_5 is at least eight octets long, which is a security condition for public-key ...


1

In OAEP we pad the message with $k_1$ zero bits and $k_2$ random bits. It's the zero bits which give you verification. The all or nothing gurantee means if you change anything you will flip all bits with probability 0.5 and the chances of getting $k_1$ zero bits by chance is 1 over $2^{k_1}$


1

I had this question in my homework and here how I answer it When we want to pick $d$ as a private key, we calculate it by $ed = 1\ mod\ \phi(n)$ this means d is modular multiplicative inverse of e in mod $\phi(n)$ and $\phi(n) = (p-1).(q-1)$, $p$ and $q$ are prime numbers. $\phi(n)$ is always an odd number if $e=2$, $gcd(2,\phi(n)) \neq 1 $ so there is no ...


1

The table that you cite should not be considered authoritative. There is nothing wrong with using RSA-OAEP. It is a well-studied protocol based on RSA primitives and more than twenty years of subsequent research into the nature of cryptographic security. The primary disadvantage of RSA-OAEP is that the RSA keys are less efficient than than those used by the ...


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