69
votes
Can a public key be used to decrypt a message encrypted by the corresponding private key?
Q: If you pedal backwards on a fish, does it go backwards?
A: ???
A fish is not a bicycle. Similarly, you cannot use a private key to encrypt a message or a public key to decrypt a message. They ...
51
votes
Meaning of: "'If factoring large integers is hard, then breaking RSA is hard,' is unproven"
The easiest way to think about it is to think of the contrapositive.
The statement:
if factoring large integers is hard, then breaking RSA is hard
is equivalent to the following:
if breaking ...
- 29.7k
32
votes
Meaning of: "'If factoring large integers is hard, then breaking RSA is hard,' is unproven"
The existence of a hard way does not imply there is no easy way.
There may be a number of ways to break RSA and we only need to find one of them.
One of these ways is factoring a large integer, so ...
- 742
28
votes
What is an extremely basic asymmetric cipher that I can present at the pub?
If you want to present public key cryptography to your parents or friends, then I suggest you follow some guidelines. First, don't talk about specific functions, nobody cares about SHAxxx, keep your ...
- 13.3k
17
votes
Accepted
Problem with the pseudo random number generator One-Time-Pad
You seem to have misunderstood what the key is.
In the context of symmetric encryption, the key is a shared secret: something that is known to both the sender and receiver. For OTP, the key is the ...
- 81.4k
15
votes
What are the flaws in this encryption algorithm?
This is not a secure encryption scheme. It is similar to a Hill cipher, and vulnerable to similar attacks. For instance, it is vulnerable to known-plaintext attacks: an attacker who observes a ...
D.W.♦
- 156k
15
votes
Does there exist an equivalent arithmetic circuit for each computable function?
Any computable boolean function with a fixed-length input can be computed by an arithmetic circuit. Consider any boolean function $f:\{0,1\}^n \to \{0,1\}$. Then there exists a multivariate ...
D.W.♦
- 156k
15
votes
What is an extremely basic asymmetric cipher that I can present at the pub?
A common metaphor I hear used is manufacturing a bunch of padlocks, keeping all the keys, and sending out open padlocks to anyone who wants one. Then anyone with such a padlock can send you secret ...
- 530
14
votes
Accepted
Why did RSA encryption become popular for key exchange?
There is no strong technical reason. We could have used Diffie-Hellman (with appropriate signatures) just as well as RSA.
So why RSA? As far as I can tell, non-technical historical reasons ...
D.W.♦
- 156k
14
votes
Accepted
If P=NP, are there cryptosystems that would require n^2 time to break?
Yes — in fact, the very first public-key algorithm that was invented outside an intelligence agency worked like that! The first publication that proposed public-key cryptography was "Secure ...
14
votes
Why do public key systems involve private keys?
Public key cryptography means that the entire communication between both parties is public, including the setup. Contrast this with the case of two parties $A,B$ meeting in secret, agreeing on some ...
- 13.3k
13
votes
What if p and q are not distinct in RSA Crypto System? What could go wrong?
The security of RSA relies on the fact that the best known way to compute $\phi(n)$ is to prime factorize $n$. For $n=pq$, where $p$ and $q$ are large, distinct primes, this is very hard. If instead $...
- 231
13
votes
Can a public key be used to decrypt a message encrypted by the corresponding private key?
Yes, a message which has encrypted using private key can be decrypted using the public key.
In fact, this is implemented to verify the authenticity of the data. In the digital signature, a person ...
- 141
13
votes
Accepted
How are extremely large integers stored and implemented in programming languages?
MPI stands for Multiple Precision Integer. Multiple precision arithmetic is what you need when you work with integer types that go beyond the machine width $w$.
The basic idea is simple, you represent ...
- 3,252
11
votes
What if p and q are not distinct in RSA Crypto System? What could go wrong?
In addition to SBareS's answer, let me mention that the formula $\varphi(pq) = (p-1)(q-1)$ only works if $p \neq q$: $\varphi(p^2) = p(p-1)$. Therefore if $p = q$ then decryption wouldn't be the ...
- 275k
11
votes
Problem with the pseudo random number generator One-Time-Pad
Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator
No, no and once again no. I'm concerned that this is what you're being taught. The absolutely fundamental ...
- 1,602
10
votes
Meaning of: "'If factoring large integers is hard, then breaking RSA is hard,' is unproven"
One additional way to look at it, is that breaking RSA requires only a special case of factoring, which may or may not be easy regardless of the general question of factoring.
As a simple example, ...
- 20.6k
10
votes
Accepted
1-to-1 cryptographically secure bit shuffling
This is known as a one-way permutation. The "permutation" refers to the first of your two requirements; the "one-way" refers to the second of your two requirements. There are various candidate ...
D.W.♦
- 156k
10
votes
Why did RSA encryption become popular for key exchange?
Diffie–Hellman lacks a crucial feature: authentication. You know you are sharing a secret with someone, but you can't know if it's the recipient or a man in the middle. With RSA, you may have a ...
- 1,040
10
votes
What are the flaws in this encryption algorithm?
Cryptosystems which are algebraic in nature are amenable to algebraic cryptanalysis.
If you are trying to design a secure cryptosystem for actual use, there is one important maxim that you should ...
- 275k
10
votes
Accepted
Does there exist an equivalent arithmetic circuit for each computable function?
Arithmetic circuits compute a polynomial in their input. An arithmetic circuit over some field $\mathbb{F}$ with $n$ variables and total degree $d$ can compute functions
$f:\mathbb{F}^n\rightarrow\...
- 13.3k
10
votes
Accepted
Can you prevent a man in the middle from reading the message?
Can the man in the middle not just take the keys swapped by the opponents, change the keys and then decrypt and encrypt the message again?
Yes, they can.
A key exchange protocol like (the "textbook" ...
- 4,979
9
votes
Running an algorithm on data remotely and ensuring answer has not been tampered with
In the crypto community, this task is known as delegated computation, or verifiable delegation. You wish to let the server (the "cloud") to do the work for you, but you also want the cloud to give you ...
- 20.6k
8
votes
Accepted
Is time complexity more important than space complexity?
In fact, when we are talking about algorithms in general, time-complexity is discussed much more frequently than space-complexity. Let me provide a few ideas to support that more general phenomenon ...
- 38.6k
7
votes
Meaning of: "'If factoring large integers is hard, then breaking RSA is hard,' is unproven"
It means that the RSA problem seems (at this time) to be more specific than factoring.
So the RSA problem is this: knowing a semiprime $pq$ and some exponent $e,$ and a value $v,$ find the $m$ such ...
- 366
7
votes
Accepted
Do one way function exist?
No known cryptographic hash functions are provably secure. It might seem to be hard to reconstruct an input hashing to a given hash value, but we can't prove that it is indeed very hard. We can just ...
- 275k
7
votes
Accepted
One way recurrence O(N)->O(1)
There are two answers: one that solves your problem, and one that answers your question. I'll start with the first. One way to make sure that previous states cannot be backtracked from generated ...
- 4,282
7
votes
Zero-knowledge proof: Abstract example
I believe this is done to illustrate two things.
(i)
The small probability, that $P$eggy ($P$rover) might be lying. If she really does not know the magic word and $V$ictor ($V$erifier) sees her ...
- 138
7
votes
What is an extremely basic asymmetric cipher that I can present at the pub?
The problem with explaining asymmetric cyphers (and the reason why most pop explanations actually fail to explain anything) is that they are entwined with the idea that there exist problems that are (...
- 4,222
7
votes
Problem with the pseudo random number generator One-Time-Pad
A pseudorandom generator is a deterministic algorithm, which given a short random seed returns a pseudorandom string fooling certain adversaries (i.e. such adversaries will not be able to distinguish ...
- 13.3k
Only top scored, non community-wiki answers of a minimum length are eligible