61 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 ...
user avatar
50 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 ...
user avatar
  • 29.1k
33 votes
Accepted

How does an operating system create entropy for random seeds?

The title and the body of your question ask two different questions: how the OS creates entropy (this should really be obtains entropy), and how it generates pseudo-randomness from this entropy. I'll ...
user avatar
31 votes
Accepted

Given RSA, why do we not know if public-key cryptography is possible?

We don't know for sure that RSA is safe. It could be that RSA can be broken in polynomial time, for example if factoring can be done efficiently. What is open is the existence of a a provably secure ...
user avatar
31 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 ...
user avatar
  • 684
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 ...
user avatar
  • 13.2k
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 ...
user avatar
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 ...
user avatar
  • 141k
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 ...
user avatar
  • 141k
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 ...
user avatar
14 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 $...
user avatar
  • 241
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 ...
user avatar
  • 141k
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 ...
user avatar
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 ...
user avatar
  • 13.2k
12 votes

NP Problems with unique solution

Yes, the class is called UP (the U standing for "unambiguous"). David points out in the comments that another answer is US. UP: If $x \in L$, then there is exactly one "proof" ("witness", "...
user avatar
  • 4,009
12 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 ...
user avatar
  • 3,162
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 ...
user avatar
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 ...
user avatar
  • 1,582
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, ...
user avatar
  • 20.4k
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 ...
user avatar
  • 141k
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 ...
user avatar
  • 965
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 ...
user avatar
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\...
user avatar
  • 13.2k
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" ...
user avatar
  • 4,899
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 ...
user avatar
  • 20.4k
9 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 ...
user avatar
7 votes

In RSA, must $p$ and $q$ have the same number of bits?

The RSA method works regardless of the size of the individual primes $p,q$. The reason that we would want $p$ and $q$ to be of roughly equal size is that one method of breaking RSA is factoring $n = ...
user avatar
7 votes

Can systems that prevent double-spending (e.g. crypto-currencies) be used to attach other unique data?

In theory, yes, a peer-to-peer validation network could be used to enforce any unique content (not just money) assuming a sufficiently large validation network. "Sufficiently large" is the catch. ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 366

Only top scored, non community-wiki answers of a minimum length are eligible