Talk:Schmidt-Samoa cryptosystem

Cryptography: Computer science Mid‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
Mid	This article has been rated as Mid-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as Mid-importance).

Severe errors in the article[edit]

This article is currently a mess and needs the attention of someone who is familiar with the scheme. I.e. the claim "Unlike Rabin this algorithm does not produce an ambiguity in the decryption at a cost of encryption speed" seems to contradict the description of the encryption $c\equiv m^{N}{\pmod {N}}$ . For this step to be a permutation N would have to be relatively prime to $\varphi (N)$ , but this is clearly not the case for $N=p^{2}q$ . Hence, as can easily be verified, decryption generally fails. It is also unclear why this cryptosytem is relevant. 83.79.189.91 (talk) 18:38, 3 August 2010 (UTC)[reply]

I have implemented this algorithm and tested encrypt/decrypt cycles, it does in fact work. Read the paper I cited. Tomstdenis (talk) 00:07, 4 August 2010 (UTC)[reply]

You were right the decryption was modulo pq not N. My bad. Tomstdenis (talk) 10:18, 4 August 2010 (UTC)[reply]

Yup, this change fixes the problem with the decryption. I still have problems with this claim:

"Unlike Rabin, though, there are no ambiguous solutions to the decryption, which means that padding and other structural identifiers are not required."

The main reason for using paddings in e.g. RSA is to avoid deterministic encryption (i.e. chosen plaintext attacks) and to prevent chosen ciphertext attacks. This cryptosystem is (as described in the paper) also susceptible to these attacks. In particular, a chosen ciphertext attacks may disclose the secret key. The paper proposes a key exchange for which the author claims that no padding is necessary. Similar protocols for a key exchange with no padding exist for RSA too. In both cases this is a property of the key exchange protocol and not the underlying cryptosystem. Rabin's cryptosystem needs two bits of overhead to distinguish which of 4 roots is the correct plaintext. This cryptosystem needs at least log(p) bits overhead (i.e. the message should be in the range 1 .. N and maybe a few bits more since the public key cannot disclose N) so that the message is unambiguous. —Preceding unsigned comment added by 81.62.72.9 (talk) 10:59, 8 August 2010 (UTC)[reply]

I don't think you need padding if the message is co-prime to $pq$ and smaller than it. You do need padding to make it non-deterministic though you're quite right. If we know that we're picking 'p' and 'q' to be roughly the same size say 336 bits each (to get a 1k-bit N) then we need only make sure that 'm' is less than $2^{328*2}$ or simply 82 bytes long at most [with randomized padding]. —Preceding unsigned comment added by Tomstdenis (talk • contribs) 10:22, 10 August 2010 (UTC)[reply]