Re: Averaging RSA ciphertexts - inferences

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 set of RSA defined primes. The
difference in the statistical properties of the distributions 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.
4.1 Question: How close are the properties of two distributions?
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

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

.

Relevant Pages

• Reconstructing p from RSA outputs?
... RSA is irrelevant except as a source of random bits. ... Then generalize to any bit pattern p. ... the filtered subset of ciphertexts is likely true, for RSA and for a random ... different from the distribution of noise generated by the RSA cipher. ...
(sci.crypt)
• Re: RSA implementation
... Why not just crack RSA ciphers using classical frequency ... More often than not RSA is used to encrypt a synchronous cipher key ... ciphertexts and at least 1 byte per possible ciphertext to count them. ... (or any other linear approximation methods) ...
(sci.crypt)
• Re: Averaging RSA ciphertexts
... The public key is used to encrypt a number of arbitrary plaintexts in the standard manner. ... Select the ciphertexts that match the bits of p in more than or equal to 1/2 the bits of p. ... Use the ciphertexts that satisfy the filter rule. ... This would be true for any bit pattern p and source of random ciphertexts. ...
(sci.crypt)