# Tag Info

### 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 ...

### 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 ...

### 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 ...

### 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 ...
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 ...

### 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 ...

### 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 ...

### 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 ...
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 ...
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 ...

### 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 ...

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" ...

### 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 ...
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 ...

### 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 ...
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 ...
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 ...

### 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 ...