# Reconstructing p from RSA outputs?

*From*: "kentucky" <pam@xxxxxxxxxxxx>*Date*: Thu, 22 Jun 2006 01:24:29 +0930

I assume the "limit" is as the number of messages increases without

bound.

Yes

6. Question:

Why is this so?

This would be true for any bit pattern p and source of random

ciphertexts. RSA is irrelevant except as a source of random bits. Try to

prove it for p=all zeros. Then generalize to any bit pattern p.

I do not know (at this time) how to proceed with a proof.

However, I can demonstrate that it is true when p=all zeros.

It seems, that you suspect that the consequence (reconstruction of p) from

the filtered subset of ciphertexts is likely true, for RSA and for a random

bit source generally?

Question: What do you think of the following inferences:

1. There exists a subset of RSA ciphertexts created with p, that always

approximate p, under averaging, as previously described?

2. There exists a non-exponential procedure by which the required subset of

ciphertexts from which p can be reconstructed, can be found without any

prior knowledge of p, q, or n?

3. As a first thought, the procedure may exploit the fact that the

distribution from which p is selected (RSA defined primes) is statistically

different from the distribution of noise generated by the RSA cipher. This

implies that the those ciphertexts that carry a strong image of the

contaminant digital signal p may be distinguished from those ciphertexts

that carry only a weak image of p. Ciphertexts with a strong image of p are

those that satisfy the aforementioned filter and have a significant

similarity to the statistical properties of the set of RSA defined primes.

The

difference in the statistical properties of the distributions (p-primes and

RSA output)

may be used to identify the ciphertexts that carry the strongest evidence of

having been

selected from the general population of RSA primes?

4. If the two distributions are very close then the chances of a successful

run of the procedure will be low otherwise the ciphertexts carrying p

can be distinguished and used to reconstuct p (as demonstrated below).

4.1 Question: How close are the properties of two distributions.

That is p-primes and RSA output?

4.2 Question: Was there an RSA requirement that p should be chosen from the

same distribution as one that we would characterise as having come from a

"random source"?

"Mike Amling" <nospam@xxxxxxxxxx> wrote in message

news:F_Vlg.256$7i.63@xxxxxxxxxxxxxxxxxxxx

kentucky wrote:

1. Scenario:

You are given a valid RSA public key.

The public key is used to encrypt a number of arbitrary plaintexts in the

standard manner.

Ciphertexts are the result.

Assume (for now) that you know the value of p. "p" is the bit pattern

used in n = p*q.

2. Filter Rule:

Select the ciphertexts that match the bits of p in more than or equal to

1/2 the bits of p.

The comparison in done against the lower 1/2 of the ciphertexts.

3. Summing the Filtered subset:

Use the ciphertexts that satisfy the filter rule.

Discard (for now) the rest as too noisy digital versions of p.

Lay the ciphertexts on upon the other.

Sum the bits in the lower 1/2 of the ciphertexts.

Divide each sum by the number of ciphertexts that satisfied the filter

rule.

The results are real valued and have 0 <= magnitude <= 1, and oscillate

closely about 1/2.

4. Recoding the real values:

Recode the real values from the previous step as follows:

If the real value is < 1/2, output a 0.

If the real value is >= 1/2, output a 1.

5. Observation:

The output of the recoding step matches p, in the limit.

I assume the "limit" is as the number of messages increases without

bound.

6. Question:

Why is this so?

This would be true for any bit pattern p and source of random

ciphertexts. RSA is irrelevant except as a source of random bits. Try to

prove it for p=all zeros. Then generalize to any bit pattern p.

--Mike Amling

.

- Prev by Date:
**Entropy of p-primes: Is this what is expected?** - Next by Date:
**Re: Entropy of p-primes: Is this what is expected?** - Previous by thread:
**Entropy of p-primes: Is this what is expected?** - Next by thread:
**Extremely Fast Verification of Public-Key System** - Index(es):