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
679 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 ...
8
votes
0answers
151 views
+150

Algorithm for Boneh and Durfee attack on RSA

I am trying to understand various attacks on RSA and I believe that they only way to fully understand the algorithm is to implement it. I am trying to implement the code in this paper (pdf) (Private ...
8
votes
0answers
446 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
52 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 ...
4
votes
0answers
195 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
66 views

How common are weak RSA keys?

There exist certain attacks that can be used against RSA keys whose prime factors are of specific forms, such as one by Coppersmith. How common are these RSA keys? If you generate primes randomly, ...
3
votes
0answers
28 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
47 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
139 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
107 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
117 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
411 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

Bitwise method of generating r for RSA-KEM

It seems that RSA-KEM has a very troublesome method of generating the secret $r$. It seems that the random value needs to be in the range $0 \le r \le {n - 1}$. Now most cryptographic environments ...
2
votes
0answers
45 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 ...
2
votes
0answers
63 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
82 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 ...
2
votes
0answers
91 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
97 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
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
104 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
178 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 ...
2
votes
0answers
110 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 ...
2
votes
0answers
222 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
105 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
102 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
153 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
33 views

How to use OpenSSL command line utility to encrypt data with encrypted key from public key?

I may not be asking the right question. I am fairly new to data encryption. I am currently being sent encrypted data that's stored as follows: [ [keysize] [key encrypted with public key] [ivsize] ...
1
vote
0answers
20 views

Should we use exponent 3 in RSA-OAEP?

As I understand it the proof that RSA-OAEP is secure in the random oracle model is much tighter for exponent 3. Does that mean that exponent 3 should be chosen?
1
vote
0answers
50 views

Encryption & decryption of integers using modular multiplicative inverse and extended euclidean algorithm

I'm looking for a neat algorithm, which is capable of encrypting an integer to another integer and decrypting it again AND is secure. When I was in university, my professor showed me an awesome way ...
1
vote
0answers
61 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
53 views

Is there a fast implementation of RSA for Microcontrollers?

Zhe Liu, Johann Großschädl, and Ilya Kizhvatov. "Efficient and Side-Channel Resistant RSA Implementation for 8-bit AVR Microcontrollers" describes a fast implementation, but only contains a sketch of ...
1
vote
0answers
23 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
80 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
60 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 = ...
1
vote
0answers
51 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 ...
1
vote
0answers
92 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
36 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
88 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 ...
1
vote
0answers
67 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
43 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
74 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
34 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
479 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$ $σ' ...
1
vote
0answers
74 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 ...
1
vote
0answers
104 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
396 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
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
124 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
267 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 ...