---

Hej alle

Jeg har lavet et modelprogram til RSA-kryptering. Jeg lavede det
i Java, men det gjorde sært, og så ville jeg lige kontrollere det
i C. Nu ved jeg ikke om jeg skal være begejstret for at det giver
samme resultat.

Jeg har beregnet at følgende tre tal hører sammen:
437 , 23 (privat), 551 (offentlig).

Her er programmet, og bagefter følger uddrag af en kildetekst og
den krypterede, dekrypterede tekst:
(Note: Jeg får en advarsel om UTF8, men jeg orker ikke at rette
på det i slutteksten.)

// RSA - kryptering

#include <stdio.h>
FILE *indfil, *udfil;
typedef int testT; // Til testformål

void encrypt (testT key, char *indfilnavn, char *udfilnavn) {
   testT ngl=437, tmp;
   unsigned char ch;
   int n;

   indfil=fopen(indfilnavn,"rb");
   udfil=fopen(udfilnavn,"wb");
   do {
      ch=fgetc(indfil);
      tmp=1;
      for (n=0; n<key; ++n) tmp=(tmp*ch)%ngl;
      fputc(tmp,udfil);
   } while (! feof(indfil));
   fclose(udfil);
   fclose(indfil);
}

int main(){
   encrypt(23,"Test.txt","T2.txt");
   encrypt(551,"T2.txt","T3.txt");
   return 0;
}


Prøvetekst:
==========
// RSA

import java.io.*;
import java.math.*;


abstract class Help {

   static long findPrimtal (long kandidat) {
      long limit;
      boolean prim;
      kandidat-=2;
      do {

Sluttekst:
=========
¶¶ OSA

import jaEa.io.*;
import jaEa.math.*;


abstra2t 2lass .blp {

?stati2 loTg fiTdrimtal ôloTg kaTdidat) {
??loTg limit;
??boolbaT prim;
??kaTdidat-=2;
??do {



--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:

> Her er programmet, og bagefter følger uddrag af en kildetekst og
> den krypterede, dekrypterede tekst:
> (Note: Jeg får en advarsel om UTF8, men jeg orker ikke at rette
> på det i slutteksten.)

Den advarsel burde du nok kigge nærmere på. Jeg kan ikke lige
koge noget sammen der virker, men jeg er da kommet så lang at
der ikke er problemer når man holder sig væk fra filsystemet.
Problemet ligger sikkert i læsning/skrivning af filer i forskellig
format - ascii ind den ene gang og noget andet den anden gang.
(hint: ch er unsigned char og tmp er int).

Ulrik Magnusson

---

Ulrik Magnusson skrev:

>> (Note: Jeg får en advarsel om UTF8

>Den advarsel burde du nok kigge nærmere på.

Det var ved afsendelsen af indlægget. Begge programmer (C og
Java) kompileres fint og kører fejlfrit. De gør bare ikke det jeg
vil have dem til.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:

> Ulrik Magnusson skrev:
> >> (Note: Jeg får en advarsel om UTF8
> >Den advarsel burde du nok kigge nærmere på.
> Det var ved afsendelsen af indlægget. Begge programmer (C og
> Java) kompileres fint og kører fejlfrit. De gør bare ikke det jeg
> vil have dem til.

Med at "kigge nærmere på" mente jeg mere noget i retning af
at bruge den som hint til fejlsøgningen. Anyway, det lykkedes
det at lave en, så vidt jeg ved, fungerende Java version
(Problemet lå i kombinationen af readByte/writeChar/
readChar/writeByte):

ADVARSEL: Java kode

class RSA
{
static void encrypt( java.io.DataInputStream in,
java.io.DataOutputStream out, int key )
throws java.io.IOException
{
int ngl = 437;
while( in.available() > 0 )
{
byte ch = in.readByte();
int tmp = 1;
for( int n = 0; n < key; ++n )
{
tmp= (tmp*ch)%ngl;
}
out.writeChar( tmp );
}
in.close();
out.flush();
out.close();
}

static void decrypt( java.io.DataInputStream in,
java.io.DataOutputStream out, int key )
throws java.io.IOException
{
int ngl = 437;
while( in.available() > 0 )
{
char ch = in.readChar();
int tmp = 1;
for( int n = 0; n < key; ++n )
{
tmp= (tmp*ch)%ngl;
}
out.writeByte( tmp );
}
in.close();
out.flush();
out.close();
}

public static void main( String[] args )
throws java.io.IOException
{
java.io.DataInputStream in;
java.io.DataOutputStream out;
in = new java.io.DataInputStream( new
java.io.FileInputStream("RSA.java") );
out = new java.io.DataOutputStream( new
java.io.FileOutputStream("RSA.java_en") );
encrypt( in, out, 23 );
in = new java.io.DataInputStream( new
java.io.FileInputStream("RSA.java_en") );
out = new java.io.DataOutputStream( new
java.io.FileOutputStream("RSA.java_de") );
decrypt( in, out, 551 );
}
}

Ulrik Magnusson

---

Ulrik Magnusson wrote:

> Anyway, det lykkedes
> det at lave en, så vidt jeg ved, fungerende Java version
> (Problemet lå i kombinationen af readByte/writeChar/
> readChar/writeByte):

Ja, ok - og nu en version som også accepterer æøå:
(readUnsignedByte i stedet for readByte() i encrypt() ):

Advarsel: Java kode

class RSA
{
static void encrypt( java.io.DataInputStream in,
java.io.DataOutputStream out, int key )
throws java.io.IOException
{
int ngl = 437;
while( in.available() > 0 )
{
int ch = in.readUnsignedByte();
int tmp = 1;
for( int n = 0; n < key; ++n )
{
tmp= (tmp*ch)%ngl;
}
out.writeChar( tmp );
}
in.close();
out.flush();
out.close();
}

static void decrypt( java.io.DataInputStream in,
java.io.DataOutputStream out, int key )
throws java.io.IOException
{
int ngl = 437;
while( in.available() > 0 )
{
char ch = in.readChar();
int tmp = 1;
for( int n = 0; n < key; ++n )
{
tmp= (tmp*ch)%ngl;
}
out.writeByte( tmp );
}
in.close();
out.flush();
out.close();
}

public static void main( String[] args )
throws java.io.IOException
{ //æøå
java.io.DataInputStream in;
java.io.DataOutputStream out;
in = new java.io.DataInputStream( new
java.io.FileInputStream("RSA.java") );
out = new java.io.DataOutputStream( new
java.io.FileOutputStream("RSA.java_en") );
encrypt( in, out, 23 );
in = new java.io.DataInputStream( new
java.io.FileInputStream("RSA.java_en") );
out = new java.io.DataOutputStream( new
java.io.FileOutputStream("RSA.java_de") );
decrypt( in, out, 551 );
}
}

Ulrik Magnusson

---

Ulrik Magnusson wrote:

> int ch = in.readUnsignedByte();
> int tmp = 1;
> for( int n = 0; n < key; ++n )
> {
> tmp= (tmp*ch)%ngl;
> }
> out.writeChar( tmp );
^^^
Du har samme grundliggende problem, som Bertil: 'tmp' er en int, og
afhængigt af hvor stor, 'ngl' er, vil der ikke være plads i en char
til resultatet.

-Claus

---

Claus Rasmussen wrote:

> Ulrik Magnusson wrote:
>
> > int ch = in.readUnsignedByte();
> > int tmp = 1;
> > for( int n = 0; n < key; ++n )
> > {
> > tmp= (tmp*ch)%ngl;
> > }
> > out.writeChar( tmp );
> ^^^
> Du har samme grundliggende problem, som Bertil: 'tmp' er en int, og
> afhængigt af hvor stor, 'ngl' er, vil der ikke være plads i en char
> til resultatet.

heh, jeg må indrømme at jeg har meget svært ved at gennemskue
om du overhovedet har ret (selv om jeg umiddelbart vil give dig det),
og hvorvidt problemet vil blive løst 100% ved at bruge writeInt()
(og readInt() i decrypt() metoden ) i stedet.

Ulrik Magnusson

---

Ulrik Magnusson wrote:

> Claus Rasmussen wrote:
>
> > Ulrik Magnusson wrote:
> >
> > > int ch = in.readUnsignedByte();
> > > int tmp = 1;
> > > for( int n = 0; n < key; ++n )
> > > {
> > > tmp= (tmp*ch)%ngl;
> > > }
> > > out.writeChar( tmp );
> > ^^^
> > Du har samme grundliggende problem, som Bertil: 'tmp' er en int, og
> > afhængigt af hvor stor, 'ngl' er, vil der ikke være plads i en char
> > til resultatet.
>
> heh, jeg må indrømme at jeg har meget svært ved at gennemskue
> om du overhovedet har ret (selv om jeg umiddelbart vil give dig det),
> og hvorvidt problemet vil blive løst 100% ved at bruge writeInt()
> (og readInt() i decrypt() metoden ) i stedet.

Hvilket det ved nærmere eftertanke helt sikkert vil, hvis
den grundliggende krypteringsalgoritme ellers fungerer - en
int er en int og kan skrives med writeInt() og læses med readInt().
De mere matematisk sindede kan måske lige bekræfte at det
faktisk _er_ et problem at smide 2 øvre bytes væk i resultatet?

Ulrik Magnusson

---

Ulrik Magnusson wrote:

> De mere matematisk sindede kan måske lige bekræfte at det
> faktisk _er_ et problem at smide 2 øvre bytes væk i resultatet?

Der behøves ikke noget matematik for at indse det. Prøv at læs i den
anden del af tråden, hvor jeg krypterer strengen "hej med dig". De
to e'er giver et overflow, og når jeg dekrypterer igen, bliver resul-
tatet 'hbj mbd dig'.

-Claus

---

Claus Rasmussen wrote:

> Ulrik Magnusson wrote:
>
> > De mere matematisk sindede kan måske lige bekræfte at det
> > faktisk _er_ et problem at smide 2 øvre bytes væk i resultatet?
>
> Der behøves ikke noget matematik for at indse det. Prøv at læs i den
> anden del af tråden, hvor jeg krypterer strengen "hej med dig". De
> to e'er giver et overflow, og når jeg dekrypterer igen, bliver resul-
> tatet 'hbj mbd dig'.

Ahem, nu er char i Java og C jo 2 forskellige ting (denne tråd
burde måske flyttes til dk.edb.programmering eller java gruppen?),
og problemet er jo at den krypterede fil bliver dobbelt så stor ved
writeInt/readInt kombinationen. Men jeg tror nu også at
writeChar/readChar er "premature optimization".

Ulrik Magnusson

---

Ulrik Magnusson wrote:

> Ahem, nu er char i Java og C jo 2 forskellige ting

I hvert fald ikke mere forskellige end at Bertels to udgaver (i C
og Java) gav det samme fejlagtige resultat.


> Men jeg tror nu også at
> writeChar/readChar er "premature optimization".

Det er ikke en optimering. Det er en fejl.

-Claus

---

Claus Rasmussen wrote:

> > Men jeg tror nu også at
> > writeChar/readChar er "premature optimization".
> Det er ikke en optimering. Det er en fejl.

"premature optimization" er ikke optimering - det ligner det
bare og resulterer i fejl.

Ulrik Magnusson

---

Ulrik Magnusson wrote:
> Claus Rasmussen wrote:
>
>>> Men jeg tror nu også at
>>> writeChar/readChar er "premature optimization".
>> Det er ikke en optimering. Det er en fejl.
>
> "premature optimization" er ikke optimering - det ligner
> det bare og resulterer i fejl.

Det er optimering på et tidspunkt i programmets levetid,
hvor det endnu ikke er modent til optimering. "Fejlen" eller
ulempen er dels, at man ofte bruger tid på at optimere ting,
som senere viser sig slet ikke at være en flaskehals, dels
at det ofte gør det sværere at ændre sit program til for eksempel
at anvende andre datastrukturer.

--
Jens Axel Søgaard

---

Ulrik Magnusson wrote:
> De mere matematisk sindede kan måske lige
> bekræfte at det faktisk _er_ et problem at smide 2 øvre
> bytes væk i resultatet?

Med de tal, som Bertel bruger må definitions- og
værdimængder være:

kryptering : 0..436 -> 0..436
dekryptering : 0..436 -> 0..436

Så når man stopper et tal mellem 0 og 255 (en char)
ind i krypteringsalgoritmen, kan man godt få et tal ud
som ikke kan repræsenteres af en char.

En mulig løsning er, at lade det hårde arbejde blive udført
af en funktion kaldet 'RSA' (den som nu kaldes encrypt).
Lad RSA arbejde på tabel af heltal.

Lad så 'krypter' indlæse chars, gemme dem i en liste af
heltal, kalde 'RSA' og endelige skrive heltallene i en fil.

Lad 'dekrypter' indlæse heltallene til en tabel, kalde 'RSA',
og udskrive resultates som tegn.

Problemet er, at 'krypter' og 'dekrypter' ikke har samme slags
input; man er altså nødt til at bide i det sure æble og lave
to forskellige funktioner.

--
Jens Axel Søgaard

---

Jens Axel Søgaard wrote:
> En mulig løsning er, at lade det hårde arbejde blive udført
> af en funktion kaldet 'RSA' (den som nu kaldes encrypt).
> Lad RSA arbejde på tabel af heltal.
>
> Lad så 'krypter' indlæse chars, gemme dem i en liste af
> heltal, kalde 'RSA' og endelige skrive heltallene i en fil.
>
> Lad 'dekrypter' indlæse heltallene til en tabel, kalde 'RSA',
> og udskrive resultates som tegn.
>
> Problemet er, at 'krypter' og 'dekrypter' ikke har samme slags
> input; man er altså nødt til at bide i det sure æble og lave
> to forskellige funktioner.

Problemet er også at det ikke længere er RSA og meget let at bryde.
Input, output og nøgle skal have samme blokstørrelse, i dette tilfælde
16 bit.

Ivan Johansen

---

Ulrik Magnusson skrev:

>og hvorvidt problemet vil blive løst 100% ved at bruge writeInt()
>(og readInt() i decrypt() metoden ) i stedet.

Den udskiftning lavede jeg ret hurtigt.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:

> Her er programmet, og bagefter følger uddrag af en kildetekst og
> den krypterede, dekrypterede tekst:

Du har i hvert fald to problemer. Det første er, at dit program
ikke engang kopierer filerne korrekt, hvis du slår krypteringen
fra (prøv det). Årsagen er, at din input-fil ikke går i EOF før
_efter_ du har forsøgt at læse ud over enden på filen.

Den rigtige måde at styre loopet på er sådan her:

int ch;
while ((ch = fgetc(indfil)) != EOF) {
...
}

Bemærk at 'ch' skal erklæres som en int, da EOF har værdien -1.

Det andet problem (at det /stadig/ ikke virker , kan jeg umiddel-
bart ikke hjælpe dig med, medmindre du har noget mere info omkring
den algoritme, du bruger.

-Claus

---

Claus Rasmussen wrote:

> Det andet problem (at det /stadig/ ikke virker , kan jeg umiddel-
> bart ikke hjælpe dig med, ...

Ok, så fandt jeg ud af det også: Prøv at lade være med at skrive 'tmp'
til en fil som en char. Skriv den i stedet til standard output som en
int. Jeg har prøvet med teksten "hej med dig" og får følgende output:

35
423 <- Ups større end hvad der kan være i en char
83
147
86
423 <- Samme problem
123
147
123
174
126
79

Når jeg kører programmet med output til fil, bliver det endelige resultat
af krypteringen/dekrypteringen "hbj mbd dig". Det er lige præcist de to
tegn, der ikke kan være i en char, der afviger fra det forventede.

-Claus

---

Claus Rasmussen skrev:

>Ok, så fandt jeg ud af det også:

Tak skal du have. Det er mit grunddesign der er forkert. Om igen
....

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Claus Rasmussen wrote:

> Bemærk at 'ch' skal erklæres som en int, da EOF har værdien -1.

- Macro: int EOF
This macro is an integer value that is returned by a number of
narrow stream functions to indicate an end-of-file condition, or
some other error situation. With the GNU library, `EOF' is `-1'.
In other libraries, its value may be some other negative number.

This symbol is declared in `stdio.h'.

---

Bertel Lund Hansen wrote:
> Jeg har lavet et modelprogram til RSA-kryptering. Jeg lavede det
> i Java, men det gjorde sært, og så ville jeg lige kontrollere det
> i C. Nu ved jeg ikke om jeg skal være begejstret for at det giver
> samme resultat.
>
> Jeg har beregnet at følgende tre tal hører sammen:
> 437 , 23 (privat), 551 (offentlig).

Du har ngl=437, hvilket vil sige at du som output får værdier i
intervallet 0-436. Du er derfor nødt til at bruge en blokstørrelse på 16
bit, både som input og output. Så i stedet for at læse og gemme 8 bit,
skal du læse og gemme 16 bit.

Ivan Johansen

---

Ivan Johansen skrev:

>Du har ngl=437

Ja, det burde jeg selv være kommet i tanker om for længst.

Jeg har en fungerende rutine baseret på Ulriks javaprogram hvor
en int er garanteret til at fylde 4 byte, og jeg benytter
writeInt() og readInt() der svarer dertil.

>bit, både som input og output. Så i stedet for at læse og gemme 8 bit,
>skal du læse og gemme 16 bit.

Krypter: læs en byte, producer en int/long.
Dekrypter: læs en int/long, producer en byte.

Den krypterede fil fylder 4 gange så meget som originalen.

Både algoritmen og dataformatet kan sikkert optimeres, men det er
jeg ligeglad med. Det skal ikke være andet en en demo.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:
> Krypter: læs en byte, producer en int/long.
> Dekrypter: læs en int/long, producer en byte.
>
> Den krypterede fil fylder 4 gange så meget som originalen.
>
> Både algoritmen og dataformatet kan sikkert optimeres, men det er
> jeg ligeglad med. Det skal ikke være andet en en demo.

I så fald er det ikke en demo af RSA. Selv om du bruger en 16 bit nøgle
får du kun 8 bit kryptering da din blokstørrelse på input er 8 bit. Du
kunne derfor lige så godt have valgt 8 bit nøgler.

Var det så ikke bedre at
Krypter: læs int/long, producer en int/long.
Dekrypter: læs en int/long, producer en int/long.

Ivan Johansen

---

Ivan Johansen skrev:

>Var det så ikke bedre at
>Krypter: læs int/long, producer en int/long.
>Dekrypter: læs en int/long, producer en int/long.

Jeg kikker på det.

Min ligegladhed går på om det kan blive hurtigere/mere elegant.
Korrekthed er noget andet.

PS. Jeg er ikke helt ligeglad med optimeringer alligevel.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen <nospam@lundhansen.dk> skrev:

Det oprindelige problem er løst, men jeg vil lige knytte en
kommentar til koden.

> void encrypt (testT key, char *indfilnavn, char *udfilnavn)

Når en funktion modtager pointere som argumenter, bør det altid
nævnes i prototypen hvis funktionen ikke ændrer det som de peger
på. I det aktuelle eksempel burde der således stå:

void encrypt (testT key, const char *indfilnavn, const char *udfilnavn)

Fordi:

- Det gør programmet lettere at læse og forstå.

- Det giver mulighed for at kalde funktionen med eksisterende
pointere til const.

- Det giver oversætteren bedre mulighed for at finde fejl.

- Det giver i visse tilfælde oversætteren mulighed for bedre
optimering.

---

"Bertel Lund Hansen" <nospam@lundhansen.dk> skrev i en meddelelse
news:mm04ou44rj9uf6ehbebgciv8a00j3ssd56@news.telia.dk...
> Hej alle
>
> Jeg har lavet et modelprogram til RSA-kryptering. Jeg lavede det
> i Java, men det gjorde sært, og så ville jeg lige kontrollere det
> i C. Nu ved jeg ikke om jeg skal være begejstret for at det giver
> samme resultat.

Dav Bertel...

Jeg ved at du har jo fået løst dit problem med RSA, men jeg tog det som en
øvelse i C++.
Ligesom du selv var inde på har jeg heller ikke gjort noget ud af at bl.a.
test om fil-operatioenerne gik godt osv.
Iøvrigt - er algoritmen som du skitserer, måden at lave RSA kryptering på
? - kan du oplyse mig om hvordan man beregner nøglerne ?

Med venlig hilsen
Torben W. Hansen



// RSA - kryptering
#include <fstream>

typedef unsigned short testT; // Til testformål - for øjeblikket 16 bit

void encrypt(testT key, char *indfilnavn, char *udfilnavn, bool mode)
{
unsigned long n;
testT ngl=437, ch=0, tmp;

ifstream indfil(indfilnavn);
ofstream udfil(udfilnavn);

while(!indfil.eof())
{
tmp = 1;
if(mode)
{ // Kryptér
indfil.read(&ch, sizeof(char));
for (n=0; n<key; ++n) tmp=(tmp*ch)%ngl;
udfil.write(&tmp, sizeof tmp);}
else
{ // Dekryptér
indfil.read(&ch, sizeof tmp);
for (n=0; n<key; ++n) tmp=(tmp*ch)%ngl;
udfil.write(&tmp, sizeof(char));
}
}
indfil.close();
udfil.close();
}


int main()
{
encrypt(23,"Test.txt","T2.txt", true); // true = Kryptér
encrypt(551,"T2.txt","T3.txt", false); // false = Dekryptér
return 0;
}