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.

learn more… | top users | synonyms

10
votes
0answers
617 views

Who first published the interest of more than two prime factors in RSA?

Multi-prime RSA is now a well known technique (described here): it uses $k>2$ distinct secret prime factors in the public RSA modulus, with the advantage that, using the CRT, we can gain a speed ...
7
votes
0answers
423 views

Security of RSA for paranoids with padding?

RSA for Paranoids (RSAP) (in cryptobytes v3n1), also known as Unbalanced RSA, is a variant of RSA proposed in 1995 by Adi Shamir, as a mean to increase the RSA public modulus size while keeping ...
4
votes
0answers
191 views

Ring Signature - paper/code difference in trying to solve inverse trap door function?

there is a paper on ring signatures and a python implementation of it here. The Step 4 in the paper describes $y_s = v =C_k,_v(y_1, y_2, ... y_r)$ for all $1 \leq i \leq r$ where $i \neq s$. The ...
3
votes
0answers
28 views

compact rsa private key format

As shown in Why does my SSH private key still work after changing some bytes in the file? a typical RSA private key file contains. The public modulus $n$ and exponent $e$; The private ...
3
votes
0answers
70 views

Deletion in RSA Accumulator

I am studying RSA Dynamic Accumulator and I have a question: why is simpler to calculate the new accumulator value after a deletion if is known the secret ϕ(n)? Is possible to calculate the deletion ...
3
votes
0answers
51 views

What followed findings of A. Lenstra et al. concerning shared factors of practical RSA moduli?

A. Lenstra et al. had a paper in 2012 "Ron was wrong, Whit is right", in which one reads: "What surprised us most is that many thousands of 1024-bit RSA moduli, including thousands that are contained ...
3
votes
0answers
25 views

Authenticate encrypted seed for KEM + AEAD hybrid cryptosystem

Say I want to encrypt something using RSA / KEM and an authenticated cipher. I encrypt using the following scheme: generate random seed z using ...
3
votes
0answers
41 views

IND-CCA1 RSA padding?

I've found a way to complete a task which I'd solve with passwords or by sending keys over the wire (otherwise) by using RSA's homomorphic property. I'm restricted to RSA (any padding; for hardware ...
3
votes
0answers
120 views

Relations between RSA and DLOG, factoring and DLOG

Definition: (The generalized Diffie-Hellman problem) Let $n=pq$ for two large primes $p,q$. Given $x, x^a, x^b,n$, find $x^{ab}\pmod{n}$. (1) Is there a known reduction from the GDH problem ...
3
votes
0answers
106 views

Finding algorithm: desire RSA's uniqueness and ECDSA's space efficiency

I am asking for help in finding a signature algorithm with the following property: Given a message m and a private key prikey, ...
3
votes
0answers
169 views

RSA encryption and signature padding flaw

This is Oxford's computer security exam question: Suppose that Bob has published an RSA encryption key $ke$ (retaining in secret the corresponding decryption key $kd$), and Alice has published a ...
3
votes
0answers
115 views

How much plainext could be known without reducting security of RSA?

It is known, for example, that exposing 50% of most significant bits of RSA private exponent does not provide security risk (when a small public exponent it used). So how to qualify security ...
3
votes
0answers
378 views

RSA reencryption scheme

Is there such an algorithm that would allow to upgrade the encryption of a RSA-encrypted message without revealing the plaintext to the untrusted user? Basically, such an algorithm would probably be ...
2
votes
0answers
59 views

MITM Attack on Key Exchange Protocols

I was doing research on this attack and I am wondering, why is Diffie-Hellman always associated with such an attack? ​ Aren't other public key cryptography schemes vulnerable to the same kind of ...
2
votes
0answers
53 views

Calculating Phi(M) and D for RSA decryption given p,q,e

I've been given a message in 4 digit numbers but it doesn't seem to work when I use my calculated values for phi(m) and d. If I'm correct phi(m) = (p-1)(q-1) correct? And d is given by ed = ...
2
votes
0answers
49 views

Usefulness of ability to calculate $m^{p+q}$ with RSA

I noticed that with only an RSA public key, it is possible/tractable to calculate $m^{p+q} \pmod n$ for any $m$ without knowing $p$ or $q$. Namely, $m^{p+q} \equiv m^{n+1} \pmod n$. (This follows ...
2
votes
0answers
89 views

RSA: special parameters construction

I have to show that the following construction of $q$ allows to factorize $N$ : $p \in \mathbb{P}$, the set of primes $q \gets p \cdot \left((p - 1)^{-1} \bmod e\right) \bmod e$ $k=1$ while $q \not ...
2
votes
0answers
79 views

Limit the number of private key uses for RSASSA-PKCS1-v1_5 with SHA-256 signature?

Assuming all messages and their signatures are available to the attacker, is it secure to use the same RSA private key to sign many messages (roughly $10^{6}$) via PKCS#11 ...
2
votes
0answers
75 views

CPA-security proof of “l-padded RSA” encryption scheme

The 10.9 exercise from the Katz-Lindell textbook creates a lot of confusion, let me state it here. Consider the following experiment for an algorithm $A$ and a function $l$ with $l(n) \leq 2n-2$ for ...
2
votes
0answers
25 views

Are there UFDs where the factorization problem is difficult but finding irreducibles is cheap?

Factorization of integers is hard, but finding irreducibles is expensive. Is there a ring where factorization is assumed hard but finding irreducibles is much cheaper than over $\Bbb Z$? It could ...
2
votes
0answers
74 views

RSA_DH vs ECDH implementation

In ECDH protocol is possible, naturally, to use the same algorithm for calculate a secret key for both communication parties (Alice and Bob for example). It is possible to design also a same algorithm ...
2
votes
0answers
352 views

Existential Forgery on textbook RSA signatures

Can an adversary who haven't seen the message before forge the signature of that message? The adversary has seen $σ_1 = (m_1)^d \bmod N$ and $σ_2 = (m_2)^d \bmod N$ He forges $m' = m_1\cdot m_2$ $σ' ...
2
votes
0answers
70 views

exchanging private key between service and iPhone app - digital signing

I need to do digital signing of my request data which will be sent to the server. My server sends distinct private keys to her clients after authentication and expects all responses to be digitally ...
2
votes
0answers
204 views

Defending hybrid encryption schemes against padding oracle attacks

I intend to use a generic integrated/hybrid encryption scheme for transmitting information between a client and a server. Key encapsulation: a 128-bit symmetric key is generated and asymmetrically ...
2
votes
0answers
99 views

Timing attacks against RSA, DH and AES

I have been reading about “Timing Attacks on RSA: Revealing Your Secrets through the Fourth Dimension” by Wing H. Wong. I was wondering if this attack is feasible while signing with RSA and, if yes, ...
2
votes
0answers
100 views

Is MITM possible after key exchange phase done successfully in RSA?

Is MITM attack theoretically possible after public/private key pair exchange is done successfully. Say Alice and Bob have genuine public keys of each other. Is MITM possible further during ...
2
votes
0answers
148 views

Rabin/RSA four possible messages?

Given this encryption method: $$f_{N,e} : Z^{*}_{N} \to QR(N)^{*};\quad f_{N,e}(x) = x ^{2e} \bmod N$$ I need to show that, for any $x_{0} \in Z^{*}_{N}$, there are four elements $x \in Z^{*}_{N}$ ...
1
vote
0answers
107 views

Complexity using RSA

You encrypt a message using the RSA encryption system as $t^e \pmod n$ , where $t, e < n$ and $t$ is the numerical equivalent of the message. The message is written in a $27$-letter alphabet and is ...
1
vote
0answers
46 views

Diffie-Hellman, RSA and the types of public key cryptography

Are these schemes fundamentally different? Are other schemes fundamentally different in the sense that you can do different operations with them (or the same operations, but needing different ...
1
vote
0answers
20 views

Does OEAP padding limit the size of my modulous to the size fo the hash function?

im looking at wiki at the moment as how to use oeap padding and it appears, help me out if im wrong as G(r) - expands r to the size of the padded message, I am then limited by the size of my hash ...
1
vote
0answers
64 views

Does the RSA algorithm use repeated squaring?

Simple question: in order to reduce such huge exponents in modular arithmetic, is repeated squaring used in RSA or is there a better way to implement it?
1
vote
0answers
58 views

Fingerprint RSA public key in PKCS1 format

I can't find anywhere details on how to fingerprint a public RSA key in PKCS1 format. There are a lot of examples on the internet on how to fingerprint an RSA public key in openssh format using ...
1
vote
0answers
33 views

Is it possbile to get same set of public and private keys twice while creating CSR ? If so where does the conflict happens !?

I'm new to cryptography and please clarify if my below assumption is wrong. Lets assume, that two different banks creating CSR and they get identical public and private key pairs of RSA. In such ...
1
vote
0answers
62 views

RSA Signature Forgery

We all know that x509 certificates carry a signature that represents the certificate digest encrypted by the private key of the issuer. I believe that the digest is encrypted only providing one ...
1
vote
0answers
42 views

Digital signature in a group chat scenario?

I understand that RSA is great for 1-to-1 digital signature. In the group chat of N people, other than storing and maintaining N public keys, is there a simpler way of authenticating each and everyone ...
1
vote
0answers
68 views

Is the half-homomorphic property of RSA a problem for blind RSA signatures?

For blind RSA signatures, is it problematic that RSA is half-homomorph? Take a scenario where blind RSA signatures are used for something like a voting procedure or this proposal: Lots of people, ...
1
vote
0answers
33 views

Reducing key shares in Damgård-Dupont threshold RSA

I'm working on understanding and implementing Damgård, I., & Dupont, K. (2005). Efficient Threshold RSA Signatures with General Moduli and No Extra Assumptions. Public Key Cryptography-PKC ...
1
vote
0answers
98 views

Is it possible (how difficult) to find MORE than one valid RSA signature?

Is it possible (how difficult) to find more than one valid RSA signatures for a given message m (after padded) and a public key ...
1
vote
0answers
363 views

Commutative Encryption with RSA scheme?

I wanted to know how I could manage to do what I'm going to tell you next, with the RSA encryption/decryption scheme. So Alice and Bob each have a public key $(n, e)$ and a private key $(p, q, d)$; ...
1
vote
0answers
106 views

RSA Key Blinding

I was looking the answer to the following question (Timing attack on modular exponentiation), discussing the Private Key Blinding as a countermeasure for timing attacks. Therefore I'm asking if ...
1
vote
0answers
103 views

Shor's Algorithm values

I'm working with Shor's algorithm and I have a question regarding the following step $$a^r -1 = (a^{r/2}+1)(a^{r/2}-1)=0 \pmod n$$ Now what is going to be the result if ${r/2}$ was -1? this will ...
1
vote
0answers
60 views

Smart card Strong authentication / Verification ( fingerprints)

I'm trying to make a strong authentication software and embedded software in a java card. I have found many papers and publications about the subject… too much information to process and I'm working ...
1
vote
0answers
117 views

RSA timing attack

Given an RSA implementation that uses Montgomery multiplications and CIOS exp algo, but NOT CRT. Given a decryption1 oracle that takes chosen cipher text and responds the plain text and the time it ...
1
vote
0answers
251 views

Is this a secure (and correct) sign-then-encrypt technique for transferring messages?

After reading some information on the way iMessage works I have been working on writing some code to try my hand at securely transferring messages in a similar manner and I wanted to confirm that the ...
1
vote
0answers
152 views

Distributed integer factorization?

I'm looking around for publicly published work on factorization of large numbers using distributed systems of any kind. So far I've come across the PDF "Mapreduce for integer factorization" by Javier ...
1
vote
0answers
145 views

Can you show how that RSA does/doesn't provide anonymity?

Considering a CPA-secure version of RSA where the ciphertext is just a rundom element from $Z^*_N$. Does that meet the anonymity requirement in which an cpa adversary cannot distinguish between a ...
1
vote
0answers
99 views

Is it possible to modify SSL handshakes to enable PFS while still using RSA during the handshake?

I know we could possibly be using DH key exchange, that would enable PFS. However, what if we make modifications on our SSL 3.0 handshake such that the only cipher we use is RSA for the achieving PFS? ...
1
vote
0answers
213 views

Diffie-Hellman exchange

So for a Diffie-Hellman problem, I am given the prime $p$ for the Diffie-Hellman exchange. I am also given $g$, secret number for machine as $A$, secret number for station as $B$, a Diffie-Hellman ...
1
vote
0answers
704 views

Decrypting a message without the private key using CRT

I am given 5 different encryption modulus, $N$, each ranging from 78 to 88 numbers long. Then for the encryption exponent, each has the same which is 5. Then I am given 5 different encrypted messages, ...
1
vote
0answers
459 views

RSA Attack with some known values

There is an RSA implementation which I need to attack to get the encrypted messages. Some of the values are known. Plain text value for input. So if I enter a message, say it "A", the plain text is ...