[C#] modulair machtsverheffen / inverse

[Synch]

Hallo,

voor school probeer ik in C# een simpel RSA programmaatje te maken waarmee ik zinnen kan versleutelen en ontsleutelen. Het probleem is alleen dat als ik blokken van 2 letters ipv. 1 letter gebruik en die vercijfer dan gaat het ergens fout. Dit kan bij het versleutelen of ontsleutelen zijn.Volgens mij gaat het fout bij of het modulair machtsverheffen of bij het vinden van de inverse.

Hierbij de relevante stukken code:

C#:

 public static int PowMod(int A, int B, int Mod)
        {
            int x = 0, y;
            y = (A * A) % Mod;
            for (int i = 1; i < B-1; i++)
            {
                x = (y*A) % Mod;
                y = x;
            }

            return x;
        }

C#:

        public static long GetInverseMod(long A, long p)
        {
           long a, b, q, t, x, y;
            a = p;
            b = A;
            x = 1;
            y = 0;
            while (b != 0)
            {
                t = b;
                q = a / t;
                b = a - q * t;
                a = t;
                t = x;
                x = y - q * t;
                y = t;
            }
            return (y < 0) ? y + p : y;
        }

Kan iemand mij helpen om te vinden waar het fout gaat? Alvast bedankt!

[RobIII]

Synch schreef op zaterdag 07 februari 2009 @ 20:38:
Kan iemand mij helpen om te vinden waar het fout gaat? Alvast bedankt!

De gein is dat je dat zélf prima kunt; je moet gewoon goed debuggen (Debuggen: Hoe doe ik dat?). Je stopt iets in de functie en verwacht er iets uit te krijgen. Wanneer is het goed en wanneer gaat het fout? En stap dan eens door de code heen met je debugger om te zien waar het mis gaat...

Ik mis eigenlijk nogal wat je zelf hebt geprobeerd en dat is toch wel een vereiste hier; zie ook onze Quickstart. Ik laat het topic nog even open, maar verwacht dan wel wat meer info over hoe je al hebt gespeurd naar fouten.

[ Voor 21% gewijzigd door RobIII op 07-02-2009 20:44 ]

[Synch]

Sorry die was ik vergeten..

Zelf heb ik alle stappen doorlopen bij het debuggen, en ik weet dat het fout gaat bij het modulair machtsverheffen. Hiervoor het in B bij powmod() klein gemaakt zodat ik alles door kon lopen, en wonderbaarlijk ging alles nu wel goed. Maar bij RSA is B vaak erg groot, en daar gaat het dus ergens fout. Ook zou het kunnen zijn dat D fout berekent word (de inverse), maar die gaat volgens mij wel gewoon goed.

Verder ben ik op internet gaan zoeken naar voorbeelden van hoe ik het modulair machtsverheffen zou moeten programmeren, maar ik kon er geen voorbeelden van vinden.

Ik heb echt alle stappen na gelopen maar ik zie het gewoon niet?

[RobIII]

Synch schreef op zaterdag 07 februari 2009 @ 20:53:
Maar bij RSA is B vaak erg groot, en daar gaat het dus ergens fout.

Dan probeer je het een keer met een grote waarde En ik zie dat je int's gebruikt; het is nog niet in je opgekomen dat érg grote getallen daar waarschijnlijk niet in gaan passen? Iets met overflows enzo?

Synch schreef op zaterdag 07 februari 2009 @ 20:53:
Ook zou het kunnen zijn dat D fout berekent word (de inverse), maar die gaat volgens mij wel gewoon goed.

"Zou kunnen" en "volgens mij"... uitspraken waar je niets aan hebt. Het zijn gewoon zaken die je zéker kunt weten als je je debugger hanteert. Dan hoef je niet te gissen. Meten = weten. Stop er wat waardes in, en reken ze (desnoods met een rekenmachientje bij de hand) na.

[ Voor 7% gewijzigd door RobIII op 07-02-2009 20:58 ]

[Luqq]

Zit er in C# geen biginteger class? Ikzelf was in java enorm aan het kloten toen ik een RSA implementatie aan het bouwen was, maar toen ik biginteger ging gebruiken verdwenen die als sneeuw voor de zon. Daar zit ook een modPow functie in.

[Synch]

RobIII schreef op zaterdag 07 februari 2009 @ 20:56:
[...]

Dan probeer je het een keer met een grote waarde En ik zie dat je int's gebruikt; het is nog niet in je opgekomen dat érg grote getallen daar waarschijnlijk niet in gaan passen? Iets met overflows enzo?

Tuurlijk heb ik hier aan gedacht Maar voor zover ik weet is het grootste getal wat hier kan voorkomen (bij blokken van 2 letters, dus 4 cijfers) 9999*9999 dus dat zou geen probleem moeten zijn. Maar ik zal er nog een keer naar kijken.

[...]

"Zou kunnen" en "volgens mij"... uitspraken waar je niets aan hebt. Het zijn gewoon zaken die je zéker kunt weten als je je debugger hanteert. Dan hoef je niet te gissen. Meten = weten. Stop er wat waardes in, en reken ze (desnoods met een rekenmachientje bij de hand) na.

Ook deze heb ik goed gecontroleerd en hij werkt.

Luqq schreef op zaterdag 07 februari 2009 @ 20:56:
Zit er in C# geen biginteger class? Ikzelf was in java enorm aan het kloten toen ik een RSA implementatie aan het bouwen was, maar toen ik biginteger ging gebruiken verdwenen die als sneeuw voor de zon. Daar zit ook een modPow functie in.

Thanks ik zal er eens naar kijken

[MrBucket]

RobIII schreef op zaterdag 07 februari 2009 @ 20:56:
[...]

Dan probeer je het een keer met een grote waarde En ik zie dat je int's gebruikt; het is nog niet in je opgekomen dat érg grote getallen daar waarschijnlijk niet in gaan passen? Iets met overflows enzo?


[...]

"Zou kunnen" en "volgens mij"... uitspraken waar je niets aan hebt. Het zijn gewoon zaken die je zéker kunt weten als je je debugger hanteert. Dan hoef je niet te gissen. Meten = weten. Stop er wat waardes in, en reken ze (desnoods met een rekenmachientje bij de hand) na.

Als je met de hand erg grote getallen uit wil rekenen, kan ik je Binary calculator aanraden. Dit is een programma dat met arbitrair grote getallen kan rekenen.

[Verwijderd]

Deze werkt ook wel goed:

http://www.alpertron.com.ar/ECM.HTM

[Woy]

In de aankomende versie van het .NET framework zit ieder geval wel support voor BigInteger.

Als is me goed herinner zit er in het huidige framework ook al een dergelijk class, maar om de een of andere reden is die internal gemaakt zodat je hem niet echt kunt gebruiken.

[MrBucket]

rwb schreef op zondag 08 februari 2009 @ 13:12:
In de aankomende versie van het .NET framework zit ieder geval wel support voor BigInteger.

Als is me goed herinner zit er in het huidige framework ook al een dergelijk class, maar om de een of andere reden is die internal gemaakt zodat je hem niet echt kunt gebruiken.

For the time being zou je natuurlijk al je int's in je code kunnen vervangen door longs, en dan kijken of het probleem nog steeds optreed. Zo niet, dan is de oorzaak ergens een overflow.

[Mr_Light]

power mod: (a^b) % mod;
Jouw geoptimaliseerde versie hiervan staat hier boven

doen we:

code:

        int mod = 2;        
        for(int a = 0; a < 100; a++) {
            for(int b = 0; b < 100; b++) {
                if(powMod(a,b,mod) != (a^b) % mod) {
                    System.out.println("voor a="+a+" b="+b+" gaat het fout");               
                }
            }           
        }

code:

voor a=45 b=17 gaat het fout
voor a=45 b=19 gaat het fout
voor a=45 b=21 gaat het fout
voor a=45 b=23 gaat het fout
voor a=45 b=25 gaat het fout
voor a=45 b=27 gaat het fout
voor a=45 b=29 gaat het fout
voor a=45 b=31 gaat het fout
voor a=45 b=33 gaat het fout
voor a=45 b=35 gaat het fout
voor a=45 b=37 gaat het fout
voor a=45 b=39 gaat het fout
voor a=45 b=41 gaat het fout
voor a=45 b=43 gaat het fout
voor a=45 b=45 gaat het fout
voor a=45 b=47 gaat het fout
.......

(ik weet niet wat de range van je modulo is maar 2 leek mij niet een ongebruikelijke usecase)

Daarbovenop vraag ik me af of jouw code überhaupt wel een optimalisatie is; dat loopje ziet er raar uit, de variable x ziet er nog al onnodig uit.

Verder heb ik nooit in RSA verdiept dus misschien is er in die context wel een hele andere versie van powermod(weet ik veel ). Gezien het gebrek aan documentatie bij die methode kan van alles het geval zijn.
http://reference.wolfram.com/mathematica/ref/PowerMod.html


Let wel dat ik de code heb moeten testen in java omdat ja... nau daarom. Dus draai de test zelf nog even.

GetInverseMod heb ik nog helemaal niet naar gekeken. Maar zoals elke luie programmeur kijk ik nooit verder dan mijn neus lang is

[Synch]

mr_light: ik heb de test zelf nog even gedraaid en ik kreeg idd hetzelfde resultaat... Bij rsa werk je mod n en n is altijd het product van 2 priemgetallen, n is dus minimaal 9 zucht 6. Maar 2 zou ook gewoon moeten werken. En x is inderdaad overbodig.

Ik ben er ook achter gekomen dat als ik de priemgetallen p en q kleiner maak (en daarmee dus n, oftewel de mod in powmod()) dan gaat het vaker fout. Als ik dat een bericht vercijfer en weer ontcijfer krijg ik soms maar halve zinnen of helemaal onzin terug. Ik snap er echt niks meer van.

.oisyn: die had ik gezien en dat heb ik veranderd in Math.Pow(a, b)

[ Voor 7% gewijzigd door Synch op 09-02-2009 11:34 ]

[.oisyn]

Mr_Light schreef op zondag 08 februari 2009 @ 15:48:
power mod: (a^b) % mod;
Jouw geoptimaliseerde versie hiervan staat hier boven

De ^ is de xor operator, niet machtsverheffen. Daarnaast gaat je test echt niet op die manier werken, omdat met grote machten je ver buiten het bereik van de int komt.

[ Voor 20% gewijzigd door .oisyn op 08-02-2009 17:15 ]

[Mr_Light]

.oisyn schreef op zondag 08 februari 2009 @ 17:09:
[...]

De ^ is de xor operator, niet machtsverheffen.

Daarnaast gaat je test echt niet op die manier werken, omdat met grote machten je ver buiten het bereik van de int komt.

Hihi je hebt helemaal gelijk. Het idee gaat nog steeds op, wat betreft int's die kan je wel in iets stoppen met groter bereik. De achterliggende gedachte was dat je gewoon tests er voor kan schrijven. En zeker waar het het een performance optimalisatie betreft. (je kan altijd testen tegen de on-geoptimaliseerde variant)

Synch schreef op zondag 08 februari 2009 @ 17:06:
is altijd het product van 2 priemgetallen, n is dus minimaal 9. Maar 2 zou ook gewoon moeten werken.

is 2 geen priemgetal meer?


P.S. Je kan altijd naar de code van Java's BigInteger#modPow() kijken.

[ Voor 7% gewijzigd door Mr_Light op 08-02-2009 22:51 ]

[Verwijderd]

Mr_Light schreef op zondag 08 februari 2009 @ 19:18:
[...]

is 2 geen priemgetal meer?


P.S. Je kan altijd naar de code van Java's BigInteger#modPow() kijken.

Product van 2 priemgetallen, dat is dus minimaal 2*2 = 4. Indien ze ongelijk moeten zijn 2*3 =6.

Dus waar hij die 9 vandaan haalt als minimum weet ik ook niet .

[ Voor 29% gewijzigd door Verwijderd op 08-02-2009 22:36 ]

[Synch]

Mr_Light schreef op zondag 08 februari 2009 @ 19:18:
[...]

Hihi je hebt helemaal gelijk. Het idee gaat nog steeds op, wat betreft int's die kan je wel in iets stoppen met groter bereik. De achterliggende gedachte was dat je gewoon tests er voor kan schrijven. En zeker waar het het een performance optimalisatie betreft. (je kan altijd testen tegen de on-geoptimaliseerde variant)

Het grootste wat c# volgens mij bied is een ulong, welke 64-bits is. Dit gaat dus nooit lukken aangezien je vaak werk met machten van boven bv de 500. Daarom moet het in stappen. Daarbij heb je het hier over een on-geoptimaliseerde variant? maar dit is gewoon zoals ik het geschreven heb zonder enige optimalisatie, het gaat er om dat het werkt.

Maar ik ga eens naar die java code kijken.

[Woy]

Je kan ook even hier kijken http://www.codeproject.com/KB/cs/biginteger.aspx

Dat is precies wat je nodig hebt.