Puzzel: Kan je het Spookbericht lezen?

Heb je een leuke wiskunde puzzel of een mooi vraagstuk gevonden en wil je die met ons delen? Post het hier.
Plaats reactie
hjeleas
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 03 sep 2020, 12:00

Puzzel: Kan je het Spookbericht lezen?

Bericht door hjeleas » 04 sep 2020, 10:30

Je krijgt een 'spookbericht' als prentje (zie bijlage).

Kan je met onderstaande informatie onbekende vector E achterhalen en het oospronkelijke bericht lezen?

Afbeelding

Achtergrond en meer tips, zie http://qsl.net/on4cko/

Veel succes!

Hans

Uitleg:

S is het spookbericht met waarden 0(blauw),1(geel) en 2(rood) + 'ruis' zodat vb. waarde 1 moeilijk leesbaar is.
Si is de i-de kolom van het spookbericht, waarbij:



M is het oorspronkelijk bericht 8xN met waarden 0,1 en 2 (voorbeeld hieronder)
Mi is de i-de kolom van matrix M (8x1 vector, voorbeeld hieronder)
H is een gegeven 8x8 matrix (zie hieronder)
E is een onbekende 8x1 vector (te achterhalen)

Code: Selecteer alles

     /  1    1    1    1    1    1    1    1  \
     |  1    0    1    0    1    0    1    0  |
     |  1    1    0    0    1    1    0    0  |
     |  1    0    0    1    1    0    0    1  |
 H = |  1    1    1    1    0    0    0    0  |
     |  1    0    1    0    0    1    0    1  |
     |  1    1    0    0    0    0    1    1  |
     \  1    0    0    1    0    1    1    0  /



Voorbeeld: bericht M 'HALLO', waarbij spaties in de matrix 'nul' zijn:

Code: Selecteer alles

   
    /                             \
    |  2  2  1221  2    2    1221 |      
    |  2  2  2  2  2    2    2  2 |      
M = |  1111  2222  2    2    2  2 |     
    |  2  2  2  2  2    21   2  2 |      
    |  2  2  2  2  1222 1222 1221 |     
    |                             |
    \  21212122112221122112112211 /

en vectoren:

Code: Selecteer alles

                                       T
  M1 = [ 0 2 2 1 2 2 0 2 ]                         
                                       T
  M2 = [ 0 0 0 2 0 0 0 1 ] 

    ...
 

hjeleas
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 03 sep 2020, 12:00

Re: Puzzel: Kan je het Spookbericht lezen?

Bericht door hjeleas » 11 sep 2020, 16:28

Code: Selecteer alles

    /                             \
    |  2  2  1221  2    2    1221 |      
    |  2  2  2  2  2    2    2  2 |      
M = |  1111  2222  2    2    2  2 |     
    |  2  2  2  2  2    21   2  2 |      
    |  2  2  2  2  1222 1222 1221 |     
    |                             |
    \  21212122112221122112112211 /
    
en,

Code: Selecteer alles

                          T
  M1 = [ 0 2 2 1 2 2 0 2 ]                         
                          T
  M2 = [ 0 0 0 1 0 0 0 1 ] 
    ...

zodat, als E=[ 0 0 0 0 0 0 0 0 ]T is:

Code: Selecteer alles

` Si = H x Mi + E     modulo 3

Code: Selecteer alles

  S1 = [ 11  4  6  5  5  6  4  3 ]T
  S2 = [ 2 0 0 2 1 1 1 1 ]T
  ...
  
De vraag van deze puzzel is om in 'omgekeerde' richting te werken, van het gecodeerde bericht S naar
het originele bericht M.

Omdat het prentje omzetten naar een matrix S saai werk is, vindt je deze matrix.
Pas op er zijn leesfouten (ruis), die wordt aangeduid met een '?' en de vector E is ook niet gekend

Code: Selecteer alles

    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25] [,26] [,27] [,28] [,29] [,30] [,31] [,32] [,33] [,34] [,35] [,36]
  /  0    0    0    0    2    ?    0    2    2     0     ?     ?     0     0     ?     ?     0     ?     0     0     ?     0     ?     ?     0     ?     0     ?     0     0     ?     ?     2     2     2     2
  |  2    ?    0    0    ?    ?    ?    2    2     ?     ?     2     0     0     2     ?     ?     ?     0     0     ?     ?     ?     ?     ?     ?     ?     ?     0     0     ?     ?     0     2     2     2
  |  0    2    ?    ?    ?    0    2    ?    ?     2     0     2     0     0     2     0     2     ?     0     0     0     2     ?     ?     ?     0     2     ?     0     0     0     0     2     0     0     0
S=|  2    0    2    2    ?    ?    0    2    2     0     ?     0     ?     ?     0     ?     0     2     ?     ?     ?     0     2     2     2     ?     0     2     ?     ?     ?     ?     0     ?     ?     ?
  |  0    ?    2    2    2    2    ?    2    2     ?     2     0     0     0     0     2     ?     0     0     0     2     ?     0     0     0     2     ?     0     0     0     2     2     0     0     0     0
  |  0    2    0    0    ?    0    2    0    0     2     0     ?     ?     ?     ?     0     2     ?     ?     ?     0     2     ?     ?     ?     0     2     ?     ?     ?     0     0     ?     ?     ?     ?
  |  ?    ?    ?    ?    0    0    ?    0    0     ?     0     0     ?     ?     0     0     ?     ?     ?     ?     0     ?     ?     ?     0     0     ?     ?     ?     ?     0     0     ?     0     0     0
  \  0    ?    2    2    2    ?    ?    ?    ?     ?     ?     0     2     2     0     ?     ?     2     2     2     ?     ?     2     2     0     ?     ?     2     2     2     ?     ?     ?     ?     ?     ?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Puzzel: Kan je het Spookbericht lezen?

Bericht door arie » 16 sep 2020, 09:55

Gegeven:

\(S_i = H \cdot M_i + E \mod 3\)

met:

Code: Selecteer alles

S = [
0, 0, 0, 0, 2, 1, 0, 2, 2, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 2, 2, 2, 2, 2, 1, 1, 0;
2, 1, 0, 0, 1, 1, 1, 2, 2, 1, 1, 2, 0, 0, 2, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 2, 2, 2, 0, 1, 1, 2;
0, 2, 1, 1, 1, 0, 2, 1, 1, 2, 0, 2, 0, 0, 2, 0, 2, 1, 0, 0, 0, 2, 1, 1, 1, 0, 2, 1, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 1;
2, 0, 2, 2, 1, 1, 0, 2, 2, 0, 1, 0, 1, 1, 0, 1, 0, 2, 1, 1, 1, 0, 2, 2, 2, 1, 0, 2, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1;
0, 1, 2, 2, 2, 2, 1, 2, 2, 1, 2, 0, 0, 0, 0, 2, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 2, 2, 0;
0, 2, 0, 0, 1, 0, 2, 0, 0, 2, 0, 1, 1, 1, 1, 0, 2, 1, 1, 1, 0, 2, 1, 1, 1, 0, 2, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 2;
1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0;
0, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 2, 2, 0, 1, 1, 2, 2, 2, 1, 1, 2, 2, 0, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2
];
en

Code: Selecteer alles

H = [
1, 1, 1, 1, 1, 1, 1, 1;
1, 0, 1, 0, 1, 0, 1, 0;
1, 1, 0, 0, 1, 1, 0, 0;
1, 0, 0, 1, 1, 0, 0, 1;
1, 1, 1, 1, 0, 0, 0, 0;
1, 0, 1, 0, 0, 1, 0, 1;
1, 1, 0, 0, 0, 0, 1, 1;
1, 0, 0, 1, 0, 1, 1, 0
];

De inverse van H (mod 3) is:

Code: Selecteer alles

Hinv = [
0, 1, 1, 1, 1, 1, 1, 1;
1, 2, 1, 2, 1, 2, 1, 2;
1, 1, 2, 2, 1, 1, 2, 2;
1, 2, 2, 1, 1, 2, 2, 1;
1, 1, 1, 1, 2, 2, 2, 2;
1, 2, 1, 2, 2, 1, 2, 1;
1, 1, 2, 2, 2, 2, 1, 1;
1, 2, 2, 1, 2, 1, 1, 2
];
(Links-)vermenigvuldig van bovenstaande formule met deze inverse geeft:

\(H^{-1}\cdot S_i = H^{-1} \cdot (H \cdot M_i + E) \mod 3\)

\(H^{-1}\cdot S_i = H^{-1} \cdot H \cdot M_i + H^{-1} \cdot E \mod 3\)

\(H^{-1}\cdot S_i = M_i + H^{-1} \cdot E \mod 3\)

\(M_i = H^{-1}\cdot S_i - H^{-1} \cdot E \mod 3\)

Definieer de laatste term F, dan krijgen we

\(M_i = H^{-1}\cdot S_i + F \mod 3\)

Ga er van uit dat het bronbericht M gecodeerd is in alleen 0 = achtergrond en 1 = letter, dan zoek je de F, zodanig dat voor alle i de waarde M_i ofwel 0 ofwel 1 is.
Deze aanname sluit aan bij het Excel voorbeeld in de link die je hebt gegeven (https://qsl.net/on4cko/).
Jij neemt daarentegen als letterkleur zowel 1 als 2, als dat zo is dan moeten we onze zoekmethode iets wijzigen.

Brutekracht zoeken door de \(3^8 = 6561\) mogelijkheden voor F levert

Code: Selecteer alles

F = [ 1, 0, 1, 2, 0, 2, 0, 2 ];
waardoor

Code: Selecteer alles

E = H * (-F) = [ 1, 1, 0, 1, 2, 0, 0, 1 ];
Hiermee wordt M

Code: Selecteer alles

M = [
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1;
1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0;
0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0;
0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1;
1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
];
ofwel (grafisch uitgezet):

Afbeelding

waarmee we uitkomen op

PHOEBEU

Noot:
1. In de klokkenluider van de Notre Dame komt Kapitein Phoebus voor (zie https://nl.wikipedia.org/wiki/Kapitein_Phoebus), mogelijk is dit een iets andere vertaling van die naam. Jammer dat het net niet helemaal klopt, maar de vorming van letters suggereert echter wel dat bovenstaande sleutel juist is.
2. De grafische voorstelling van de matrix loopt van onder naar boven (zoals jij hierboven aangaf in je codering van S)
3. Er zijn 3 lege horizontale rijen in M (met alleen maar nullen). Door bij E op de gewenste plaats 1 op te tellen, kan je in de text een horizontale lijn toevoegen (bijvoorbeeld E[1] = 1 + 1 = 2 maken).
4. De 2 puntjes in de eerste en in de laatste kolom kan ik niet verklaren. Mogelijk artefacten of aanhalingstekens?


Kan dit kloppen of moeten we verder zoeken ?

hjeleas
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 03 sep 2020, 12:00

Re: Puzzel: Kan je het Spookbericht lezen?

Bericht door hjeleas » 18 sep 2020, 09:18

Dag Arie,

Knap gedaan!
"PHOEBEUS" is antwoord - Proficiat in het oplossen van de puzzel!


"Phoebeus" is naast een karakter uit de klokkeluider van de Notre Dame van Victor Hugo ;
ook een verwijzing naar de Griekse 'Pheubeus Appolo', als 'Zonnegod' - daarom een kleine achtergrond van de puzzel hier onder.


Vriendelijke groeten,
Hans

Een kleine achtergrond van de puzzel: Ze is gebaseerd op
een vooroorlogse 'hellschreiber' (letterlijk: licht-schrijver) methode uit de radio communicatie en het moderne learning-with-errors schema,

Lichtschrijvers zijn redelijk oud ; van eenvoudige zonnewijzers terug zijn al te vinden in het oude testament (de Trap van Achaz, 2Koningen)tot recente digitale zonnewijzesrs (zonnewijzerpark van Genk.) Hellschreiber werkt met lagere frequenties maar werkt met hetzelfde idee.
De LWE (learning-with-errors) methode is een post-quantum cryptografie schema (gestandardiseerd in 2016)

Ik ben geen expert in crypto, maar combinatie van de twee technieken leek me wel iets .

Het is interessant te weten dat brute force gebruikt werd om tot een oplossing te komen ; Het zou in principe de enigste methode moeten zijn.

ps.
Ik maakte helaas een foutje bij matrix 'S' : De "aanhalingtekens" die je vermeldt zijn stukjes van de laatste letter, want
om de ruis te maken voor het LWE schema, zond ik het woord 'PHOEBEUS' volcontinue uit via een SDR als 'PHOEBEUSPHOEBEUSPHOBEUS...'
en capteerde deze als spectogram om matrix S te bekomen; Om analyse moeilijker te maken vermeed ik (regelmatige) witruimte tussen de letters en plakte ik de laatste 'S' van PHOEBEUS aan de 'U'.

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Puzzel: Kan je het Spookbericht lezen?

Bericht door arie » 18 sep 2020, 13:30

hjeleas schreef: ...
Het is interessant te weten dat brute force gebruikt werd om tot een oplossing te komen ; Het zou in principe de enigste methode moeten zijn.
...

Dan het slechte nieuws:

Je definieert:

\(S_i = H \cdot M_i + E \mod 3\)

met:

Code: Selecteer alles

S = [
0, 0, 0, 0, 2, 1, 0, 2, 2, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 2, 2, 2, 2, 2, 1, 1, 0;
2, 1, 0, 0, 1, 1, 1, 2, 2, 1, 1, 2, 0, 0, 2, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 2, 2, 2, 0, 1, 1, 2;
0, 2, 1, 1, 1, 0, 2, 1, 1, 2, 0, 2, 0, 0, 2, 0, 2, 1, 0, 0, 0, 2, 1, 1, 1, 0, 2, 1, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 1;
2, 0, 2, 2, 1, 1, 0, 2, 2, 0, 1, 0, 1, 1, 0, 1, 0, 2, 1, 1, 1, 0, 2, 2, 2, 1, 0, 2, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1;
0, 1, 2, 2, 2, 2, 1, 2, 2, 1, 2, 0, 0, 0, 0, 2, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 2, 2, 0;
0, 2, 0, 0, 1, 0, 2, 0, 0, 2, 0, 1, 1, 1, 1, 0, 2, 1, 1, 1, 0, 2, 1, 1, 1, 0, 2, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 2;
1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0;
0, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 2, 2, 0, 1, 1, 2, 2, 2, 1, 1, 2, 2, 0, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2
];
Bij elke spatie/lettertussenruimte in het bericht is \(M_i\) de nulvector.
Dan reduceert de codering tot

\(S_i = H \cdot \begin{bmatrix}0\\ 0\\ \vdots \\ 0\end{bmatrix} + E = E\mod 3\)

Zoek daarom naar gelijke kolommen in S die regelmatig over S verdeeld zijn, en naast alle letterbreedtes heb je dan ook direct sleutel E te pakken:

Afbeelding

waarmee dit cryptosysteem gebroken is...

Plaats reactie