Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

Code ontcijferen

Wat is de formule voor het volgende probleem: een code bestaat uit 3 getallen. 3 personen krijgen ieder 1 deel van de code. Deze code valt echter met 2 personen al op te lossen. Hoe ziet dan de formule eruit als deze 2 getallen worden ingevoerd en de 3e dus hiermee wordt bepaald?
reactie
De oplossing is een naar mijn mening een lineaire vergelijking waarbij het derde cijfer wordt bepaald door het snijpunt in de y-as van een horizontale lijn dus waarbij het derde cijfer (0,y) is.

Mikel
Student hbo - maandag 9 april 2007

Antwoord

Beste Mikel,

Ik snap je oplossing niet helemaal. Maar ik vermoed dat het overeenkomt met waar ik hieronder uitkom. Jij zegt de: de oplossing is een lineaire vergelijking. In 2dimensies is dat een lijn en in 3dimensies is dat een vlak. Gezien het vervolg denk ik dat je 2D bedoeld. Dan krijg je dus: y=ax+b. Ik vermoed dat jij bedoelt dat a en b de eerste twee getallen zijn. Want vervolgens wil je het derde cijfer berekenen als snijpunt met de y-as. Maar dat is (x,0) en niet (0,y). En wat bedoel je met "horizontaal"). Maar goed, je krijgt dan 0=ax+b en dus x=-b/a. Dit betekent dat je met a en b het derde getal (x) kunt berekenen. Maar ook met x en b het eerste (a=-b/x), etc. Dat is inderdaad waar ik op uitkom. Je kunt alleen naar eenvoudiger formules zoeken (hoewel dat een kwestie van smaak is). Maar je moet in ieder geval nog aangeven hoe je de code dan berekent. Toch?


==================

Vragen over codes zijn altijd intrigerend. En het concept van een code die je met twee van de drie mensen kunt oplossen maar alleen niet vind ik mooi bedacht.

Het probleem met codes is wel dat (voor mij in ieder geval) een beetje onduidelijk blijft wat je nou eigenlijk probeert op te lossen. Welk deel van je informatie is publiek (en kun je dus gebruiken om de code te ontcijferen) en welk niet? Etc. Ik wil proberen dat een beetje helderder te maken.

Volgens mij kun je een code zien als een functie. De invoer bestaat in dit geval uit drie getallen (x, y en z). De uitvoer is in principe het ontcijferde bericht. Maar, het kan ook een sleutel zijn waarmee een bericht is te ontcijferen. Dus we hebben het over een functie f(x,y,z).

Nu zeg jij dat de code door ieder tweetal te ontcijferen is. Dat betekent mi dat er functies f1, f2 en f3 zijn zdd f1(x,y)=f2(y,z)=f3(x,z)=f(x,y,z) voor elk mogelijk verstrekt drietal x, y en z. Maar je wilt (neem ik aan) dat de code niet door één persoon te ontcijferen is. Dat betekent dat er voor elke x minstens twee (maar eigenlijk heel veel) drietallen ((x,y1,z1), (x,y2,z2), etc) moeten zijn zdd f(x,y1,z1) en f(x,y2,z2) verschillende resultaten opleveren. En analoge condities voor y en z.

Je kunt vragen: Aan welke voorwaarden moet f voldoen dat dit mogelijk is? In ieder geval zie je dat dit eisen stelt aan het domein van f. Wan stel dat elk paar x,y elke z mogelijk is. Dan mag f(x,y,z)=f1(x,y) dus niet afhangen van z. De waarde van z doet er dus niet toe. Maar aangezien x en z er wel samen uit moeten kunnen komen betekent dat x er alleen ook uit kan komen. En dat was niet de bedoeling.

Het simpelste is als er bij elk paar x,y maar één waarde van z mogelijk is (z=h(x,y)). Als x en y bij elkaar komen kunnen ze z berekenen en dan f(x,y,z). Maar als x en z bij elkaar komen kunnen ze ook uitzoeken welke waarde van y er nodig is. Etc. De voorwaarde is dan wel dat er voor ieder paar z,z maar één y is zdd z=h(x,y).

In principe is de voorwaarde niet zo strikt. Er mogen voor elk paar x,y best meerdere z zijn (z1, z2, ...) mits f(x,y,z1)=f(x,y,z2)=.... Dus het bovenstaande is geen voorwaarde voor f. Maar, ik heb nog niet de indruk dat dit interessantere codes oplevert.

Het bovenstande betekent dat het domein van f een oppervlak is in de driedimensionale ruimte. En wel zo dat je voor ieder paar x,y precies een z vindt zodat (x,y,z) op het oppervlak ligt, en iedem voor de andere paren. De simpleste mogelijkheid hiervoor is m.i. een vlak dat niet evenwijdig loopt aan de x-, y- of z-as. B.v. het vlak: x+y+z=100.

Maar, dan blijft nog steeds de vraag watvoor functie f dan moet zijn. Want, als x, y en z bekend zijn moet je ook nog (een sleutel om) de code (te) ontcijferen. Niet ieder functie kan. Niet geschikt is f(x,y,z)=x+y. Neem b.v. z=10 en x=20. Als deze twee bij elkaar komen vinden ze (met het bovenstaande vlak): y=70 en dus f=90. Naar stel nu eens dat x = 50. Dan vindens ze: y=40 en dus weer f=90. Wat voor waarde x ook heeft f is altijd 100-z. En dus kan z de code ook alleen ontcijferen.

De laatste voorwaarde was dat er voor elke x minstens twee (maar eigenlijk veel) paren y1,z1 en y2,z2 zijn zdd f(x,y1,z1) en f(x,y2,z2) verschillen. Ik stel voor: f(x,y,z) = xyz. Als nu z bekend is vind je y=100-x-z en dus: f=x·(100-x-z)·z. Bekijk je dit nu als functie van x dan zie je dat dit een parabool is die nul oplvert voor x=0 en x=100-z en daartussen (een heleboel) verschillende waarden van f (mits z niet nul is). Door de symmetrie zie je nu meteen dat aan de laatste voorwaarde ook is voldaan voor y en z.

Even samenvatten: We maken publiekelijk bekend dat x+y+z=100 en dat f(x,y,z)=xyz. Nu kun je z een random getal nemen (tussen 0 en 100?). En vervolgens het paar x,y zoeken zdd x+y=100-z en xy = f/z. Met f de sleutel die je wit overbrengen. Je geeft x,y en z hun code. Als er twee bij elkaar komen kunnen ze de derde berekenen en vervolgens de sleutel.

Het bovenstaande verhaal geeft bij lange na niet alle mogelijke functies f die geschikt zijn voor jouw code. Maar zelfs met deze moet je oppassen. x, y en z mogen niet 0 zijn. Want dan weet je meteen zeker dat de uitkomst 0 is. Maar ook als b.v. z=2 weet z dat f maximaal gelijk kan zijn aan 492·2=4802. Je moet er wel voor zorgen dat hij aan die informatie niets heeft.

Nou. Ik ben benieuwd of je hier wat aan hebt....

Groet. Oscar

os
zondag 15 april 2007

©2001-2024 WisFaq