Public key cryptography describes all cryptographic algorithms which have a pair of keys, one key that performs encryption and one key that performs decryption. One of these keys is made available publicly, allowing anyone to send messages that only the holder of the private key can read. You should ...
4
votes
2answers
207 views
What is the appropriate public key encryption for secure coin flipping?
I quote Bobby's question here since I encountered the same one...
Random Coin Flip using ElGamal and a Trusted Party
Consider the following protocol for two parties to flip a fair coin.
Trusted ...
4
votes
2answers
413 views
Is a RSA-signature of some identifying data a safe way to implement a license key?
I have this idea of implementing a license key:
After the user downloads the program, he connects to a website and sends his Windows product ID.
The website, then, sends this back to him with a ...
4
votes
2answers
348 views
Random Coin Flip using ElGamal and a Trusted Party
An old exam question I am trying to figure out:
Consider the following protocol for two parties to flip a fair coin.
Trusted party T publishes her public key pk
A chooses a random bit ...
4
votes
2answers
2k views
In RSA, do I calculate d from e or e from d?
In the original paper introducing RSA, it is implied that one should first choose $d$ and then calulate $e$ from $p$, $q$, and $d$. However, I have found in other places (such as the wikipedia article ...
4
votes
2answers
407 views
How do I solve this RSA instance for m?
How we can solve this equation and get the value of M?
$$8 = M^{13} \mod 33$$
not a computer program, but a mathematical operation.
4
votes
1answer
220 views
Why is Diffie-Hellman considered in the context of public key cryptography?
In all textbooks I used the Diffie-Hellman key exchange is under "public key cryptography".
As far as I can see it is a method to exchange a key to be used with a symmetric cryptographic algorithm, ...
4
votes
1answer
185 views
Why does RSA give better security on longer messages?
I am trying to understand the notion of RSA security.
Choosing a public exponent where $e = 3$ facilitates the calculations, considering that it is secure if the plaintext or message is long.
If the ...
4
votes
3answers
540 views
ElGamal: Multiplicative cyclic group and key generation
Here on the ElGamal wikipedia page http://en.wikipedia.org/wiki/ElGamal_encryption
Alice generates an efficient description of a multiplicative cyclic group G, of order q, with generator g.
How ...
4
votes
1answer
98 views
Client and server using same SSL certificate - any issues?
I'm working on software where multiple components will communicate with each other using SSL.
There would be one central component acting as a server, which would also require the clients to present ...
4
votes
1answer
101 views
Correct method to encrypt data so that it can be decrypted only by Alice and Bob
I need to build a system that stores encrypted transactions. Transaction involves always two parties. Payer and payee. Both must be able to download encrypted transaction from server and decrypt it ...
4
votes
1answer
136 views
Question about why RSA is hard to attack
I think I understand why RSA is hard to attack but I'd like to get clarification if I actually do.
Assume there are two people, Alice and Bob, who are attempting to communicate privately but that we ...
4
votes
1answer
180 views
How are trapdoor functions developed/found and where can I find existing ones?
Trapdoor functions are a fundamental part of public key cryptography. An example of the most common trapdoor is
Prime Factorization, used in cryptosystems such as RSA
How are these trapdoor ...
4
votes
2answers
318 views
Is this a correctly formatted PGP session key packet?
RFC 4880 may be full of information, but it can be incredibly vague at times, so im looking for someone who actually knows the answer to this.
Given this public key:
...
4
votes
3answers
248 views
Preventing message replay with RSA
I am using RSA to encrypt some data but I would like to eliminate the possibility of message replay. By message replay I mean sending a valid message multiple times to the original recipient. It is ...
3
votes
3answers
4k views
RSA encryption with private key and decryption with a public key
Does the encryption with a private key and decryption with a public key works in RSA? Is it done when we use RSA for sender authentication ?
Thanks.
3
votes
2answers
515 views
Can a computationally unbounded adversary break any public-key encryption scheme?
Assume there is a public-key encryption scheme $(KeyGen, Enc, Dec)$ with perfect correctness (i.e., for all messages M and valid key-pairs (PK,SK), we have $Dec_{SK}(Enc_{PK}(M))=M$).
Will there ...
3
votes
3answers
617 views
What is the importance of Modular arithmetic in cryptography?
Why do we use modular arithmetic so often in Cryptography?
3
votes
2answers
232 views
If Bob steals Alice's private key, how exactly would he read her encrypted documents?
So Bob grabs Alice's secret key when she isn't looking and her encrypted files, doesn't he need to know her passphrase to read her files?
What I am reading is that no he does not need it but as far ...
3
votes
6answers
311 views
Is there an authenticated encryption scheme where the recipient can attribute the message to a single sender?
With a standard authenticated encryption scheme (or MAC), Alice and Bob share a symmetric key. When Alice sends something to Bob, Bob can check that it is authentic. At that point, Bob can deduce ...
3
votes
2answers
290 views
Can RSA encryption produce collisions?
In RSA, a message is encrypted by $m^e \pmod N$. $N$ is the modulus, $m$ is the message and $e$ is the public exponent. (I know that $m$ should not be greater than $N$.)
My question is, can $m^e$ be ...
3
votes
2answers
142 views
Can one have an authentic, but repudiable, message without a previously shared secret?
Bob wants to send a message to Alice, such that Alice can be sure that the message came from Bob, but can't prove it to anyone else.
If I understand right, this means that the same message could have ...
3
votes
2answers
338 views
Difference between symmetric and asymmetric hash function?
The Linux kernel supports symmetric and asymmetric hash functions. E.g. sha1, sha256, ...
See tcrypt.c and search for test_hash_speed and ...
3
votes
3answers
222 views
How to avoid a chicken and egg scenario with encrypting passwords?
I am working on application that allows users to upload files containing company data and then share those files with a list of other users that have specific roles within the system.
I want to ...
3
votes
1answer
168 views
What's the main difference between Pohlig-Hellman and RSA?
Both Pohlig-Hellman and RSA perform encryption and decryption by exponentiation modulo some integer ($p$ prime for PH, $n$ composite for RSA). They both use a key $e$ as the exponent to encrypt a ...
3
votes
2answers
245 views
Key space size when either of two public keys are valid for authentication?
If for authentication a user can own either A OR B public key instead of just one specific key is that equivalent to halving the key space. i.e. it it theoretically twice as easy to brute force and ...
3
votes
4answers
912 views
How are timestamps verified?
You put an input and the hash value comes as an output then when someone puts the input the hash function it is applied to see if it is the same hash original value is stored in some database , that ...
3
votes
2answers
466 views
Difficulty of breaking RSA for a given key size
Is it true that breaking a 1024-bit RSA key is as difficult as breaking a 128 bit symmetric key (e.g. AES)? I know that breaking a RSA key is equivalent to factoring the modulus $N$. To factor it, you ...
3
votes
1answer
598 views
RSA: If n=35, show that e will equal d
Show that if $n = 35$ is used as an RSA modulus then the encryption exponent $e$
always equals the decryption exponent $d$?
What I have so far:
$n = 35$
Therefore $p = 5$ and $q = 7$ or vice versa, ...
3
votes
3answers
428 views
public key cryptography and digital signature
I read the following from Understanding Public Key Cryptography on Microsoft TechNet:
Using a private key to establish identity shows that the full
encryption and decryption operation was ...
3
votes
1answer
133 views
When is an asymmetric scheme considered broken?
Does the following quote imply that valid encrypted data can be created and decrypted by someone other than the owner of a private key:
An asymmetric encryption scheme is considered to be broken ...
3
votes
1answer
238 views
What is the computational cost of a public key certificate signature verification?
What is the computational cost of a certificate signature verification in terms of exponentiation, multiplication and other computation operations?
3
votes
2answers
3k views
When to use RSA and when ElGamal asymmetric encryption
If i am not wrong in cryptography there are 2 basic cryptographic schemes for public key cryptography. RSA encryption whose security is based on the infeasibility of solving the factoring of big ...
3
votes
1answer
158 views
What is the property of RSA where N=e?
In RSA, suppose we know that $e=N$ and we are given the value of $e$.
($N = p\cdot q$ for some large primes $p$ and $q$; $\gcd(e, \varphi(N) = 1)$
Can we calculate $d$ ($d = e^{-1} \mod ...
3
votes
2answers
100 views
How can the Schmidt–Samoa cryptosystem uniquely decrypt large messages?
Suppose I choose $p=7$ and $q=11$.
This gives a public key of $p^2·q = 539$.
However, decryption occurs using a modulus of $p·q=77$.
If a person chooses to encrypt $500$ using my public key, how ...
3
votes
1answer
135 views
Signature scheme with two private keys, neither derivable from the other
Is there any scheme, ideally one widely used or at least widely available, where you can treat both the signing and verifying keys as secret?
Basically, the functionality I'm looking for is this:
...
3
votes
1answer
112 views
Combining AEAD with RSA
'Hybrid' encryption, where we combine symmetric encryption with public-key cryptography, is pretty 'tried and tested'.
To summarise, we generate a symmetric key and encrypt it using RSA. We would ...
3
votes
1answer
249 views
Get RSA PlainText without Knowing Private Key
If I have an algorithm,RSA-Crack(), that, for a given RSA public key (n,e), is able to decrypt 1% of the messages encrypted with that key (without knowledge of the corresponding private key).Can there ...
3
votes
1answer
59 views
In a lattice, how can one define a good basis and a bad basis?
When it comes to lattice based cryptographic systems, all the literature talks about, good bases and bad bases.
How does one define what a good basis is and what a bad basis is?
3
votes
3answers
173 views
Are asymptotic lower bounds relevant to cryptography?
An asymptotic lower bound such as exponential-hardness is generally thought to imply that a problem is "inherently difficult". Encryption that is "inherently difficult" to break is thought to be ...
3
votes
1answer
138 views
Secure encrypt-then-sign with RSA
I understand that when you want to encrypt and sign data with RSA the generally recommended approach is sign-then-encrypt.
However, I have encrypted data that I need to sign, to prove the author of ...
3
votes
1answer
118 views
DGK Cryptosystem Key Generation and Decryption Issues
I detailed here the DGK (Ivan Damgård, Martin Geisler and Mikkel Krøigaard) cryptosystem, and I managed to get it to work, most of the time...
The BIG problem that I am facing at the moment is that ...
2
votes
2answers
954 views
How much computing resource is required to brute-force RSA?
It's been over 30 years since Rivest, Shamir and Adleman first publicly described their algorithm for public-key cryptography; and the intelligence community is thought to have known about it for ...
2
votes
3answers
227 views
How can one sign with NTRU?
I am looking at implementing NTRU, but I noticed that while the encryption/decryption algorithm seems to be mature and well-documented, there is comparatively little information about how to sign ...
2
votes
2answers
492 views
Why should the RSA private exponent have the same size as the modulus?
Consider the generation of an RSA key pair with a given modulus size $n$ and a known, small public exponent $e$ (typically $e = 3$ or $e = 65537$). A common method is to generate two random primes ...
2
votes
2answers
117 views
Does a high exponent compensate for a low degree of certainty?
If a RSA certificate is created with a low degree of certainty, does the value of the exponent compensate for this?
I'm asking because certain implementations of key generation software hide the ...
2
votes
2answers
146 views
Protocol to generate Client Certificates at the start of a SSL session automatically?
A more secure form of 'cookie' could be created for SSL communications through the following method.
The client generates and requests the server to sign a certificate.
Then the client authenticates ...
2
votes
1answer
111 views
Why does key generation take an input $1^k$, and how do I represent it in practice?
In my lecture, the lecturer said:
Let $K$ be the key generation algorithm. Given a security parameter represented in unary, $1^k$, $K(1^k)$ will output a keypair $(pk; sk)$, known as the public ...
2
votes
1answer
97 views
Crypto puzzle as proof of randomness?
I need an untrusted client to generate a random public/private keypair (in particular, an Ed25519 keypair, which can be generated really fast), but I'm only allowed to see the public key. The ...
2
votes
1answer
257 views
What happens if an RSA key pair has identical public and private exponents?
Rather, is it possible for big prime numbers?
Classroom examples usually involve smaller primes, so for example if you are given a prime number pair $p = 3$, $q = 13$ you would get $n = 39$ and $e = ...
2
votes
3answers
134 views
Safety of DSA key parameters sharing
I'm looking for a solution to use in a context where I need to be able to generate new asymmetric key pairs quickly (using a widely recognized algorithm, and EC-DSA is not applicable). It sounds like ...
