---

Hej alle

Jeg er ved at skrive et demoprogram der kan lave RSA-kryptering. Jeg har et mystisk problem.

Jeg har en encrypt-metode der tager 1 char, behandler den og skriver resultatet til en fil som 4
bytes (egl. 4 'char-int'). Min decrypt-metode tager 4 char, sammensætter dem til en int, behandler
den og skriver resultatet som 1 byte ('char-int') til en fil.

Jeg har testet min algoritme i testmetoden ved at springe de led over der har med filer at gøre. Det
producerer en perfekt kopi af originalfilen. Når jeg bruger filmetoderne, er nogle af bogstaverne
forvanskede.

Er der nogen der har et bud på hvad problemet er?


Her er udpluk af tekstfilerne, original og 'kopi':
====================================
Mange dansk- og engelsktalende skriver "vira". Det er en
kunstform. Der findes intetkønsord efter 2. bøjning, men de
ender på - um (signum - signa). Hvis man lader sig inspirere
af 3. bøjning (strider mod at "virus" er 2. bøjning), burde
man foreslå "virora" eller "virera" (som er ubrugelige på dansk).

Mange dansk- og engeJsktaJende skrõver ªvõraª. Det er en
kunstform. Der fõndes õntetkønsord efter 2. bøjnõng, men de
ender på - um (sõgnum - sõgna,. Hvõs man Jader sõg õnspõrere
af 3. bøjnõng (strõder mod at ªvõrusª er 2. bøjnõng,, burde
man foresJå ªvõroraª eJJer ªvõreraª (som er ubrugeJõge på dansk,.


Her er koden:
===========

// RSA - kryptering

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


abstract class Help {
   static byte wordSize = 4; // Størrelsen på en int
   static int n, ch, tmp, value;
   static int buffer[] = new int[wordSize];

   static void encrypt (int ngl, int key, String indfil, String udfil) {
      try {
         FileReader original = new FileReader(indfil);
         FileOutputStream kryptfil = new FileOutputStream(udfil);
         ch=original.read();
         while (ch!=-1) {
            tmp=1;
            for (n=0; n<key; ++n) tmp=(tmp*ch)%ngl;
            for (n=0; n<wordSize; ++n) { buffer[n]=tmp%256; tmp/=256; }
            for (n=wordSize-1; n>=0; --n) kryptfil.write(buffer[n]);
            ch=original.read();
         }
         kryptfil.close();
         original.close();
      } catch(IOException e) { System.out.println("IO: "+e); }
   }


   static void decrypt (int ngl, int key, String indfil, String udfil) {
      try {
         FileReader kryptfil = new FileReader(indfil);
         FileOutputStream dekryptfil = new FileOutputStream(udfil);
         value=kryptfil.read();
         while (value!=-1) {
            for (n=1; n<wordSize; ++n) value=value*256+kryptfil.read();
            tmp=1;
            for (n=0; n<key; ++n) tmp=(tmp*value)%ngl;
            dekryptfil.write(tmp);
            value=kryptfil.read();
         }
         dekryptfil.close();
         kryptfil.close();
      } catch(IOException e) { System.out.println("IO: "+e); }
   }


   static void test () {
      int ngl=437, k1=551, k2=23;
      try {
         FileReader original = new FileReader("Test.txt");
         ch=original.read();
         while (ch!=-1) {
            tmp=1;
            for (n=0; n<k1; ++n) tmp=(tmp*ch)%ngl;
            for (n=0; n<wordSize; ++n) { buffer[n]=tmp%256; tmp/=256; }
            value=0;
            for (n=wordSize-1; n>=0; --n) value=value*256+buffer[n];
            tmp=1;
            for (n=0; n<k2; ++n) tmp=(tmp*value)%ngl;
            ch=original.read();
         }
         original.close();
      } catch(IOException e) { System.out.println("IO: "+e); }
   }
}



class RSA_Keys {
   static BufferedReader indtast =
      new BufferedReader(new InputStreamReader(System.in));

   public static void main(String args[]) throws IOException {
      System.out.println("Starting RSA...");
      Help.encrypt(437,551,"Test.txt","T2.txt");
      Help.decrypt(437,23,"T2.txt","T3.txt");
//      Help.test();
   }
}


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

---

Bertel Lund Hansen wrote:

> Jeg er ved at skrive et demoprogram der kan lave RSA-kryptering. Jeg har et mystisk problem.
> Jeg har en encrypt-metode der tager 1 char, behandler den og skriver resultatet til en fil som 4
> bytes (egl. 4 'char-int'). Min decrypt-metode tager 4 char, sammensætter dem til en int, behandler
> den og skriver resultatet som 1 byte ('char-int') til en fil.
>
> Jeg har testet min algoritme i testmetoden ved at springe de led over der har med filer at gøre. Det
> producerer en perfekt kopi af originalfilen. Når jeg bruger filmetoderne, er nogle af bogstaverne
> forvanskede.
>
> Er der nogen der har et bud på hvad problemet er?

Jeg er jo vanvittig hurtig til at kode , så her er løsningen
(som, så vidt jeg ved, fungerer):

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 );
}
}

(andre læsere: resten af diskussionen findes i
dk.adb.programmering.c)

Ulrik Magnusson

---

Ulrik Magnusson skrev:

>Jeg er jo vanvittig hurtig til at kode

Ja, det må jeg sige.

[Fra C-gruppen:]

>(Problemet lå i kombinationen af readByte/writeChar/
>readChar/writeByte):

Ja, det tænkte jeg nok.

>så her er løsningen (som, så vidt jeg ved, fungerer):

Mange tak.

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

---

Ulrik Magnusson wrote:

> Jeg er jo vanvittig hurtig til at kode , så her er løsningen
> (som, så vidt jeg ved, fungerer):

og for ikke at have noget halvfærdigt liggende, så kommer
her lige en version som tager hensyn til at ngl er en int og
at tmp derfor eventuelt kunne have en værdi som ikke passer
i en char (ved store/små værdier af ngl):
(writeInt()/readInt() i stedet for writeChar()/readChar())

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.writeInt( 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.readInt();
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 );
}
}

(andre læsere: resten af diskussionen findes i
dk.edb.programmering.c)

Ulrik Magnusson

---

Jeg har set lidt på implementationen, jeg må indrømme at jeg ikke kan
genkende RSA i den.

Så vidt jeg ved, beror RSA på valget af 2 primtal, ud fra hvilke flere
andre faktorer vælges eller beregnes, hvorved man får sin private key
der bruges til kryptering.

Nogen der vil forklare mig hvad det er jeg ikke forstår ved den
angivne implementation?

> 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.writeInt( tmp );
> }
> in.close();
> out.flush();
> out.close();
> }

Det der sker her, er vel blot en obfuskering og ikke en RSA kryptering
eller hur?

Mvh Morten

---

Morten skrev:

>Så vidt jeg ved, beror RSA på valget af 2 primtal, ud fra hvilke flere
>andre faktorer vælges eller beregnes, hvorved man får sin private key
>der bruges til kryptering.

Ja, men den del er ret simpel. Derfor postede jeg ikke koden til
det og spurgte heller ikke om det. Min testrutine benyttede 437,
23 og 551 som de tre tal, baseret på primtallene 19 og 23.
(437,23) er den offentlige nøgle, og (437,551) den private.

Tallene er naturligvis alt for små til at give nogen reel
sikkerhed. Det er kun et demoprogram (som nu kan arbejde med
vilkårlige nøgler der ikke er for store).

>Det der sker her, er vel blot en obfuskering og ikke en RSA kryptering
>eller hur?

Det er skam ægte RSA-kryptering med de angivne nøgler, bortset
fra at input og output bør være af samme bitlængde.

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

---

Bertel Lund Hansen wrote:
> Morten skrev:
>
>
>>Så vidt jeg ved, beror RSA på valget af 2 primtal, ud fra hvilke flere
>>andre faktorer vælges eller beregnes, hvorved man får sin private key
>>der bruges til kryptering.
>
>
> Ja, men den del er ret simpel. Derfor postede jeg ikke koden til
> det og spurgte heller ikke om det. Min testrutine benyttede 437,
> 23 og 551 som de tre tal, baseret på primtallene 19 og 23.
> (437,23) er den offentlige nøgle, og (437,551) den private.
>
> Tallene er naturligvis alt for små til at give nogen reel
> sikkerhed. Det er kun et demoprogram (som nu kan arbejde med
> vilkårlige nøgler der ikke er for store).
>
>
>>Det der sker her, er vel blot en obfuskering og ikke en RSA kryptering
>>eller hur?
>
>
> Det er skam ægte RSA-kryptering med de angivne nøgler, bortset
> fra at input og output bør være af samme bitlængde.
>

Takker - jeg var bare nysgerrig :)

Morten

---

Hej alle

Nu funker det - vist nok. Jeg har i hvert fald fået én rutine til at arbejde
med 16-bit format, og den samme bruges til både kryptering og dekryptering.
Jeg har været nødt til at skrive mine egne int-læse- og -skrivemetoder.

Jeg har i indlægget udvidet min linjelængde til 78 og ombrudt nogle
udskriftlinjer som ellers blev for lange, men koden er lige til at kompilere.

Den metode der genererer nøgler, er lidt primitiv, men principielt rigtig nok.
Den kan bare ikke sikre at nøglerne er store nok. De burde jo også være på 16
bit.


// RSA-kryptering - nøgleberegning samt kryptering og dekryptering
// Bertel Lund Hansen, sep. 2002

import java.io.*;


class RSA {

// ======== Trace-flag ========

static final boolean trace=false;

// ======== Hjælperutiner ========

// SIZE=4 bevirker at man somme tider løber ind i en fortegnsbit
// når to ints ganges til en long. SIZE=3 dur bare ikke.
// Der er internt brugt long-variable for at undgå et tilsvarende
// problem med int når to 16-bit værdier ganges sammen.

static final int SIZEofINT=2;

static long findPrimtal (long kandidat) {
long limit;
boolean prim;
--kandidat;
if (kandidat%2==0) --kandidat;
do {
kandidat+=2;
limit=(int) Math.sqrt(kandidat);
prim=true;
for (int div=3; div<=limit; div+=2) {
prim=kandidat%div!=0;
}
} while (!prim);
return kandidat;
}


static long gcd (long x, long y) {
long rest=y; y=x;
do { x=y; y=rest; rest=x%y; } while (rest>0);
return y;
}


static long readIntBytewise (DataInputStream ind) throws IOException {
int nr=0, n;
int readBytes[] = new int[SIZEofINT];
long value=0; // Teknisk init.
try {
for (nr=0; nr<SIZEofINT; ++nr) readBytes[nr]=ind.readUnsignedByte();
value=readBytes[0];
for (nr=0; nr<SIZEofINT; ++nr) value=value*256+readBytes[nr];
} catch (EOFException e) {
// Her ryger vi ned hvis der til sidst ikke er bytes nok at læse.
// nr registrerede hvor mange der var.
value=0;
for (n=0; n<nr; ++n) value=value*256+readBytes[n];
}
return value;
}

static void writeIntBytewise (long value, DataOutputStream ud)
throws IOException {
int nr=0;
for (nr=0; nr<SIZEofINT; ++nr) {
ud.writeByte((int) (value%256));
value/=256;
}
}


static void help () {
System.out.println
("\n RSA kan generere nøgler, kryptere og dekryptere en fil.\n");
System.out.println
(" -n T frembringer et sæt nøgler.");
System.out.println
(" T bestemmer starttallet og dermed størrelsen.\n");
System.out.println
(" -k N nøgle <indfilnavn> <udfilnavn>");
System.out.println
(" (de)krypterer indfilen og skriver til udfilen.\n");
}

// ======== Hovedrutiner ========

static void findNøgler (long tal) {
long p1, p2, nøgle, z, privat, offentlig;
p1=findPrimtal(tal);
p2=findPrimtal(p1+2);
System.out.println("Primtal: "+p1+", "+p2);
nøgle=p1*p2; z=(p1-1)*(p2-1);
// Vælg privat nøgle så privat og z er indbyrdes primiske.
privat=(int) Math.sqrt(nøgle);
while (gcd(privat,z)!=1) {
++privat;
if (trace) System.out.println("Prv: "+privat);
}
// Vælg offentlig nøgle så z går op i privat*offentlig-1.
offentlig=z;
while ((privat*offentlig-1)%z!=0) {
++offentlig;
if (trace) System.out.println("Off: "+offentlig);
}
System.out.println("Nøgler: ("+nøgle+","+privat+") -
("+nøgle+","+offentlig+")");
}

// ======== crypt tager 1 int og producerer 1 int
// Men undervejs kan der godt opstå long-værdier.

static void crypt (long ngl, long key, String indfil, String udfil)
throws IOException {
long value=0, tmp;

System.out.println("\n Krypterer ...\n");
DataInputStream in =
new DataInputStream (new FileInputStream(indfil));
DataOutputStream out =
new DataOutputStream (new FileOutputStream(udfil));
while (in.available()>0) {
value=readIntBytewise(in);
tmp=1;
for (int n=0; n<key; ++n) tmp=(tmp*value)%ngl;
writeIntBytewise((int) value,out);
}
in.close();
out.flush();
out.close();
}

// ======== main() ========

public static void main(String args[]) throws IOException {
long n=0, k=0;
int nr=0;
String temp;
char cmd;
if (args.length>0) {
String kommando=args[0];
if ( kommando.length()==1 || ("-/").indexOf(kommando.charAt(0))==-1) {
help();
System.exit(1);
}
cmd=(kommando.toLowerCase()).charAt(1);
try {
++nr; n=Long.parseLong(args[nr]);
if (cmd!='n') {
   ++nr; k=Long.parseLong(args[nr]);
    ++nr; temp=args[nr];
    ++nr; temp=args[nr];
}
} catch (Exception e) {
switch (nr) {
case 1: System.out.println
("Angiv det fælles tal (eller et starttal)."); break;
case 2: System.out.println
("N: "+n+" Angiv krypteringsnøglen."); break;
case 3: System.out.println
("Angiv den fil der skal (de)krypteres."); break;
case 4: System.out.println
("Angiv den fil der skal skrives til."); break;
}
System.exit(1);
}
switch (cmd) {
case 'n': findNøgler(n); break;
case 'k': crypt(n,k,args[3],args[4]); break;
default: help();
}
}
else help();
}

}

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

---

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

> Den kan bare ikke sikre at nøglerne er store nok. De burde jo også være på 16
> bit.

Uden andet end at have skimmet din kode, vil jeg lige sige at din
løsning vil skalere dårligt til den størrelse primtal man vil bruge i
en praktisk situation. Dette skyldes dit
"hoved-under-armen"-primtalscheck, som ganske vist er korrekt men som
vil tage MEGET lang tid for store tal.

Overvej at lave lidt research på dette emne.

--
Thorbjørn Ravn Andersen
http://homepage.mac.com/ravn

---

Thorbjoern Ravn Andersen skrev:

>Uden andet end at have skimmet din kode, vil jeg lige sige at din
>løsning vil skalere dårligt til den størrelse primtal ...

Ok ja.

>Overvej at lave lidt research på dette emne.

Nej, jeg vil ikke forbedre det yderligere (bortset fra at jeg har
fjernet den fejl at løkken blev gennemløbet uafhængigt af om
testen allerede havde kikset). Det skal ikke bruges til andet end
indlæring. Primtal har jeg tidligere gjort lidt ud af.

Men jeg er egentlig mere spændt på hvordan man optimerer
potensopløftningen. Min løkke er:

   for (int n=0; n<key; ++n) tmp=(tmp*value)%ngl;
   (hvor% er modulusberegning)

Den skalerer ad pommeren til. Hvordan kan det gøres smartere?

XFut dk.edb.programmering da problemet er helt generelt.

(svar sendes til den gruppe og kan ikke ses her)

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

---

Bertel Lund Hansen skrev:

Newsgroups: dk.edb.programmering.java, dk.edb.programmering.java

Genialt! Jeg har nu sendt det som et løst indlæg i
programmeringsgruppen. Futtet er også forkert (mangler).
Beklager.

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