[Cryptography] End-to-End, One-to-Many, Encryption Question

[Ben Laurie]

On 13 June 2014 14:46, Phillip Hallam-Baker <phill at hallambaker.com> wrote:
>
>
>
> On Thu, Jun 12, 2014 at 6:50 AM, Ben Laurie <ben at links.org> wrote:
>>
>> On 12 June 2014 07:35, Bill Frantz <frantz at pwpconsult.com> wrote:
>> > On 6/11/14 at 5:49 PM, kentborg at borg.org (Kent Borg) wrote:
>> >
>> >> Is there a way to encrypt once with key A, super-encrypt with key B1
>> >> (not
>> >> knowing any other keys), and finally decrypt with key C1 (not knowing
>> >> any
>> >> other keys)?  Or, super-encrypt with key B2, then decrypt with key C2?
>> >
>> >
>> > This problem is similar to the problem which would occur if an
>> > encryption
>> > algorithm was a group. If the algorithm is a group, then there is a key
>> > C
>> > which can decrypt a message which is encrypt(B, encrypt(A, text)). DES
>> > was
>> > proven to not be a group, making triple-DES a viable way to get the
>> > security
>> > of a longer encryption key.
>>
>> All symmetric crypto algorithms need to have keys that are not a
>> group, or there is a meet-in-the-middle attack available.
>>
>
>
> But that is another area where formal logic can fail. DES is not a group,
> but all it takes to stop something being a group is for one mapping to not
> meet the criteria.
>
> So lets say I am using the original Cesar cipher with a displacement of n
> characters, A->D, B->E, etc.
>
> This is a group because modular addition is a group.
>
> But now lets say that we have a modified cipher which has a displacement of
> n characters except that character n always maps to itself and so does the
> character that would map to it.
>
> The new cipher is not a group. But it is close enough to being a group as to
> make no difference from a cryptanalysis point of view.
>
>
> It is a similar problem with public key, people thought that an np-complete
> problem would make a good cipher till other folk showed that heuristic
> approaches break them.

I did not claim that "not a group" was sufficient. It is, however, necessary.