Questions tagged [rsa]

An asymmetric (e.g. public-key) cryptosystem, based on modular exponentiation with big exponents and modulus. RSA can be used both for signature and encryption with proper paddings.

Filter by
Sorted by
Tagged with
0
votes
1answer
49 views

What is the difference between probabilistic and deterministic prime-factor recovery function in NIST 800-56B?

In the previous standard, the deterministic was not included. It is already in the current standard. What is the reason for this? Can I use both function?
2
votes
1answer
97 views

Why is it necessary a prime factor recovery for a RSA Key-Pair Validation (in case of fix public exponens)?

In NIST 800-56B publishing, this is done with the $(p, q) = RecoverPrimeFactors (n, e, d)$ function. I don't understand why is necessary if $p$ and $q$ are known during in generation. In my opinion, ...
0
votes
0answers
27 views

What is the number of fixed plaintexts of RSA [duplicate]

Considering RSA, $n=p\,q$ with $p,q$ odd primes and the public key $(n,e)$, where $\gcd(e,\phi(n))=1$, I need a hint on how to show that the number of plaintexts with $E_e(x)=x$ equals $\gcd(e-1,p-...
5
votes
2answers
332 views

Breaking RSA with Factor in Range of $\sqrt{N}$

Suppose on of the RSA prime factors $p$ is the range of $\sqrt{N}$, in particular it holds that $|p-\sqrt{N}|<\sqrt[4]{N}$ I want to show that RSA can be broken in time poly(log N) Given hint: $N = ...
0
votes
1answer
152 views

How many points in RSA, such that $m^e = m \bmod n$

For every RSA-cryptosystem, there exist some messages $m$, for which it holds that $m^e \equiv m \pmod n$ As to the question, how many such messages exist, this question has already been asked and ...
1
vote
1answer
100 views

RSA public key identification

Consider a multi party system where public keys of all receivers are known. Server wants to send message to one of them using (textbook?) RSA. Adversary is given ciphertext and even Message to be send,...
3
votes
1answer
150 views

Does blinding protect again fault injection attack against RSA with CRT

I know that blinding can be used as a countermeasure against side-channel timing attacks on RSA-CRT: RSA Timing Attack and Prevention through blinding My question is: can blinding also be used as a ...
2
votes
2answers
180 views

How many low-order bits of an RSA modulus can we safely fix to 1?

It's easy to generate an RSA modulus $n=p\,q$ of $k$ bits with $n\equiv-1\pmod{2^\ell}$, for $\ell$ up to about $k/2$: we can choose $p$ as usual, fix the $\ell$ low-order bits of $q$ to $-p^{-1}\...
0
votes
0answers
38 views

Difficult to guess the targeted receiver

The protocol is defined as : Bob want to send message to one of his friends say $k$ friends , he does not want his others friends (except one whom he want to send message ) to tell who is targeted ...
0
votes
0answers
80 views

Why is ((m^e mod n)^d mod n) = (m^ed mod n) in RSA? [duplicate]

$$RsaPrivate(RsaPublic(m)) = (m^e \bmod n)^d \bmod n = (m^e)^d \bmod n$$ $$RsaPublic(RsaPrivate(m)) = (m^d \bmod n)^e \bmod n = (m^e)^d \bmod n$$ why is this always true?
1
vote
2answers
201 views

DHKE Square and Multiply

Given is a DHKE algorithm. The modulus 𝑝 has 1024 bit and 𝛼 is a generator of a subgroup where 𝑜𝑟𝑑(𝛼)≈2160. Assuming the public keys have already been computed, how many number of modular ...
0
votes
0answers
75 views

Can you obtain private key d and compute plaintext from El-Gamal?

Given an Elgamal encryption scheme with public parameters $k_{pub}=(p,\alpha,\beta)$ and an unknown private key $k_{pr}=d$. Due to an erroneous implementation of the random number generator of the ...
8
votes
2answers
2k views

Prime factorization (102 digits)

I have a number that consists of 102 digits and I need to factor it. I ran it in alpertrom.com.ar, but it'll take up to 40 hours if I counted all right. Is there any way to make it by hand (stupid ...
3
votes
1answer
97 views

Commitment schemes for arbitrarily large integers

My question is about commitment schemes for arbitrarily large integers. One scheme I know uses groups of unknown order (RSA or class group) and depends on the strong-RSA assumption. You chose a random ...
2
votes
1answer
90 views

RSA proof regarding m % n

I have a question regarding the proof that RSA works I understand that $m^{(ed \bmod z)} \bmod n = m \bmod n$ , but I don't understand why $m \bmod n = m$ (This question assumes m is the message, $z=(...
1
vote
0answers
79 views

RSA with Carmichael number

I've to prove that RSA still works with a public key $(e,pq)$ where p is a prime and q is a Carmichael number such that $q<p$ and $\gcd(e,(p-1)(q-1))=1$ I know how RSA works wiht $p,q$ primes but ...
1
vote
3answers
125 views

How can a recipient recognize which encrypted messages are intended for them?

Let's say there's a decentralized email service where parties' public keys are known. A sender sends a message to a recipient by encrypting via RSA with the recipient's public key and posting the ...
0
votes
1answer
64 views

Why is $\phi(N) = (p^2 -1) (q^2 - 1)$ here?

I was reading a paper on attacks on RSA variants, and the paper equates $\phi(N) = (p^2-1)(q^2-1)$. Before, I have always seen $\phi(N) = (p-1)(q-1)$ and don't understand why it is different here. I ...
1
vote
1answer
64 views

RSA message encryption question

I'm very new to cryptography, I wanted to know what exactly do I have to do to encrypt a three-letter message using RSA? for example if I wanted to encrypt this message $M= \text{HCP}, p=11 q=13$. Do ...
1
vote
1answer
147 views

Faster alternatives to RSA trapdoor permutation

We're working on web3.0 decentralized internet, a big part of which is a decentralized file storage system where clients upload files to storage providers and pay them for the services. Storage ...
0
votes
1answer
78 views

is this useful to help break RSA?

So, I'm kinda newbie in this cryptography stuff, I just like to understand complex things.A couple of months ago I was learning and I maybe found a pattern in prime numbers and their multiplications, ...
1
vote
1answer
72 views

What if the bitlength of the value evaluated in Barrett reduction is greater than 2k the modulus?

For $c\equiv a \pmod n$, in Barrett Reduction, $\mu = \lfloor{\frac{2^{2k}}{n} \rfloor}$ is precomputed, where $k = \lceil{\log_2{n}} \rceil$ and the bitlength of $a$ is assumed to be less than $2k$. ...
1
vote
1answer
155 views

Chosen Ciphertext Attack textbook RSA

I'm trying to perform a chosen-ciphertext attack against an RSA oracle. I have $c$ as the ciphertext I want to decrypt, $e$ and $n$. I already know that I could choose a number $r$, compute $r^e \cdot ...
0
votes
0answers
69 views

An "unsafe" curve over RSA? [duplicate]

I'm implementing a token server and considering backing them with ECDSA. The options from the library I'm using expose the NIST curves P-256, P-384, and P-521. The safe curves site does not list P-521,...
4
votes
5answers
3k views

Why do we use groups, rings and fields in cryptography?

I'm a student of Masters in Cyber Security. I have a habit to understand things from their first principles (at the very beginning). Kindly use any simple mathematical example to answer because I have ...
5
votes
1answer
133 views

Factorization for special primes $P$, $Q$, and $R$

Suppose that $p$, $q$, and $r$ are distinct $n$-bit primes, we define $$ \begin{array}{rcl} P & = & p \mathbin\Vert q \\ Q & = & q \mathbin\Vert r \\ R & = & r \mathbin\Vert p \...
0
votes
0answers
185 views

CNG/BCrypt/NCrypt Import an ephemeral AES key wrapped with a persistent RSA key

I will write some kind of security client/server pair: The server part provides wrapped AES keys. The client part, based on CNG win32 API (ncrypt.h+...
2
votes
0answers
61 views

How to associate a post-quantum public key with a pre-quantum one in blockchains?

As a layperson, I'm curious if a cryptocurrency could fork to a quantum-resistant algorithm without people losing access to their wallets. Is it possible to generate a quantum-resistant public key ...
0
votes
1answer
66 views

In a hybrid cryptosystem is safe to send the encrypted key together with the encrypted message?

I am encrypting a message using an hybrid cryptosystem: I encrypt my message using AES-256 and I encrypt the symmetric cipher key using RSA. The following questions come to my mind: I want to know if ...
-2
votes
1answer
400 views

How can I find d knowing c, n, e in RSA?

If I know $n,e,c$ can I find $d$ in RSA? ($n = 3174654383$ and $e = 65537$ $c=2487688703$) I saw this $d=(1/e)\bmod\varphi$ but if the numbers are getting bigger it can be hard to get $d$ in that way ...
-3
votes
1answer
213 views

Can Big Data together with deep neural networks attack RSA by affording the vast calculation of prime multiplications in advance?

This is a spin-off from Can Big Data attack RSA by just calculating many prime multiplications in advance? [duplicate]. Intro I am somewhat new to cryptography. Repeating the basics of RSA from How ...
0
votes
0answers
193 views

Attack a RSA padding scheme that appends zeros

Imagine we implement RSA padding such that a number of byte zeros are appended to the message until its length is equal to 100 (i.e. 800 bits). Also, let's assume that the public exponent $e$ is equal ...
0
votes
0answers
83 views

Can Big Data attack RSA by just calculating many prime multiplications in advance? [duplicate]

Intro I am somewhat new to cryptography. Repeating the basics of RSA from How are the primes used to generate RSA keys?: Textbooks say the one-way function is merely two primes (with some critical ...
3
votes
1answer
121 views

Order of random element in RSA is big

Im trying to understand the proof in "The Discrete Logarithm Modulo a Composite Hides O(n) Bits" by Håstad et al, where he shows that the order of a random element in RSA group is big. I got ...
2
votes
1answer
119 views

Can you break an RSA modulus if you know $k \cdot \phi(n)$ where $k$ is a large prime?

Given some RSA modulus $n$, can you factor $n$ if you are given $k \cdot \phi(n)$ where $k$ is also a large prime? (Of course, you could factor $n$ if you were given $\phi(n)$ as discussed here, but ...
0
votes
1answer
89 views

RSA Inverse Multiplication

I have $n,e$ and $c$, $p$ and $q$ are prime, but $q$ is the inverse multiplication of $e$ and $p$ so $$q = e^{-1} \bmod p$$ How can $i$ get $p$ and $q$ back?
2
votes
1answer
160 views

Are GPUs inefficient for calculations on big numbers? Is RSA and EC cypto generally done on CPU only?

Looking specifically at RSA and EC algorithms which imply doing operations on integers >= 256 bits (>> 64 bits), I have noticed (from my limited experience) that 99% of the software for ...
0
votes
0answers
84 views

Request for a zero-knowledge proof (or hint)

I want to design a zero-knowledge proof (ideally a NIZK, but could be a sigma protocol) so that Alice can prove that a certain encryption contains a value that has been signed by a certain key. More ...
0
votes
2answers
126 views

RSA decryption time

I'm currently trying to create a lua script that can handle encrypting and decrypting using RSA, but when decrypting, the program takes an extremely long time, whilst when encrypting, the program is ...
0
votes
2answers
186 views

Do perfect squares count as valid moduli for an RSA semi-prime?

The question is pretty self-explanatory but basically I just want to ask if, when choosing the p and q primes that, when multiplied, become the modulus for an RSA public key, is there a risk that ...
5
votes
1answer
583 views

What is the Lord of the Ring(s): Side Channel Attack and What are the results

A recent Paper to appear on USENIX Security 2021 titled as Lord of the Ring(s): Side Channel Attacks on the CPU On-Chip Ring Interconnect Are Practical by Riccardo Paccagnella Licheng Luo Christopher ...
0
votes
1answer
205 views

Example of breaking RSA with CRT [duplicate]

I understand that if the same message is sent to 3 people with $e=3$ that even with different public keys, the message can be decoded using the Chinese Remainder Theorem. I have tried to figure out ...
0
votes
0answers
62 views

Why if i change some characters of a Public key on authorizedKeys the login still works

This question is similar to: [1] Why does my SSH private key still work after changing some bytes in the file? But in this case (on Windows) after editing the authorized_keys file and changing some ...
1
vote
0answers
51 views

Combining ECC And RSA for a Web Based Chat system

I'm a building a Web application chat message system(Over TLS) and i would like to know if the following theory is correct. Sender I'm generating keyPairs using RSA and another KeyPairs using ECC. By ...
3
votes
1answer
164 views

What is the NTRU parameter equivalent to security level 112, 128 and 192?

I came across this paper which mentions this table, which states that NTRU 347 is equivalent to 112 bit security level However, in this paper, Choosing parameters for NTRU mentions that NTRU-401 is ...
2
votes
3answers
227 views

Factoring Anderson's RSA backdoor

In 1993, Anderson [1] proposed a backdoor to the RSA key generation algorithm. This backdoor requires that a backdoor key (prime) $A$ be implanted within the key generation portion of the RSA ...
1
vote
1answer
59 views

Reveal a plaintext with 3 encryptions of Textbook RSA

Assume we using Textbook RSA encryption with the public key $(N,3)$. How can I learn message $m$ if I have the encryptions of $m,m+1,m+2$ in an efficient way? I'm studying for a test and it's a ...
0
votes
0answers
95 views

Guarding against vulnerabilities for a digital signature service (RSA )

Lets's say I have a cipher-module / cryptography-service that signs a hash of some unknown payload. What are the possible attacks that I would need to guard against in this context (primarily assuming ...
90
votes
4answers
41k views

Does Schnorr's 2021 factoring method show that the RSA cryptosystem is not secure?

Claus Peter Schnorr recently posted a 12-page factoring method by SVP algorithms. Is it correct? It says that the algorithm factors integers $N \approx 2^{400}$ and $N \approx 2^{800}$ by $4.2 \cdot ...
0
votes
0answers
40 views

Can RSA key be determined when encrypted text is displayed alongside the clear text?

I would like to encrypt some text and display part of the encrypted text alongside the clear text as a means to prove that I generated it. For example, let's say I have the text ABCDE that I want to ...

1 2 3
4
5
49