Go Down

Topic: happy cat (Read 7576 times) previous topic - next topic

m145mcc

Jul 26, 2013, 01:56 pm Last Edit: Aug 01, 2018, 04:07 pm by m145mcc Reason: 1
ray gun

robtillaart

Does it also work with progmem strings?

Where can the lib be downloaded?


Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart

A quick look at the code resulted in these questions/remarks/improvements:

First, it is good to have this reference implementation as it can be used to check the

1) how much memory does this lib takes?
The whole table is created which costs a lot of memory. As the encryption/decryption is rather simple I think it can be captured in a few formulas.

2) The memory footprint and possible the performance can be improved to by using for (uint8_t  i=0; i< 26; i++)  as the arduino is still an 8 bitter.

3) the performance of the en/decryption is worse as the table is generated over and over again for every String.

4) The dump of the encryption table is not efficient.

5) do you have performance numbers? (chars/sec encrypted or decrypted);

6) I miss an example folder with example sketches, at least 3 sketches
  • encrypt.ino
  • decrypt.ino
  • performaceTest.ino

    5) do you have performance numbers? (chars/sec encrypted or decrypted);

    OK, now some constructive feedback ;)

    A rewrite of the view_table() function, which uses a lot less memory as it not build the table, it just calculates the value and prints it.
    in a same manner you can do the encrypt and decrypt function.

    Be aware that the UNO has only 2048 bytes of RAM and "if you have a long seed string like this between quotes" (~50 chars) your table is already more in the order of 1300 bytes.
    By using the formula approach the size is brought back to a array of 26 chars which are in alphabetical order so they can be calculated too! So no need to have any table at all.

    Code: (experimental, not tested) [Select]

    void cifra::view_table(String seed)
    {
     seed.trim();
     const int seed_len = seed.length();

     for (uint8_t i=0; i<26) Serial.print('_');
     Serial.println();

     for (uint8_t i=0; i<26) Serial.print('a' + i);
     Serial.println();

     for (uint8_t i=0; i<26) Serial.print('|');
     Serial.println();
     
     for(uint8_t i = 0; i < seed_len; i++)
     {
       for(int j = 0; j < 26; j++)
       {
         int idx = seed[i] - 'a' + j;      //  97 == 'a', you measure the distance in the alphabet
         if (idx > 26) idx -= 26;
         Serial.print('a' + idx);                 // no need for the key array, we can calculate th value
       }
       Serial.println();
     }
     Serial.println();
    }


    By making it formula based you can easily include the whole alphabet, including digits and special chars (optionally all values 0..255) Printing will be a bit more difficult.

    In short a nice start but I am eager to see version 2.0 ;)
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart


I added
Code: [Select]
#define CIFRA_VERSION "CIFRA 2.0"  
to cifra.h so you can easily keep control of the versions.

Code: (experimental) [Select]

#include <Cifra.h>

cifra test; // must create obj of class

void setup()
{
  Serial.begin(115200);
 
  while (!Serial);
 
  Serial.println("Cifra performance test");
  Serial.println("----------------------");
  Serial.println(CIFRA_VERSION);
  Serial.println();


  uint32_t start = millis();
  for(int i=0; i< 100; i++)
  {
    test.encrypt("Secret Message","PassWord");
  }
  uint32_t duration = millis() - start;

  Serial.print("100 encryptions: ");   
  Serial.print(duration/100.0, 2);   
  Serial.println(" msec per call");   
 
 
  start = millis();
  for(int i=0; i< 100; i++)
  {
    test.decrypt("~i) sj$hG(^FT`","PassWord");
  }
  duration = millis() - start;

  Serial.print("100 decryptions: ");   
  Serial.print(duration/100.0, 2);   
  Serial.println(" msec per call");
 
 
  start = millis();
  for(int i=0; i< 100; i++)
  {
    test.getKey("PassWord");
  }
  duration = millis() - start;

  Serial.print("100 getKeys: ");   
  Serial.print(duration/100.0, 2);
  Serial.println(" msec per call");
}

void loop()
{
}


Code: (output) [Select]

Cifra performance test
----------------------
CIFRA 2.0

100 encryptions: 16.53 msec per call
100 decryptions: 16.54 msec per call
100 getKeys: 15.60 msec per call


Can you run this test with the reference version ?
(you can include this test of course in the example folder)
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart

A quick look at the code shows that you still use lots of memory

Code: (from encode, decode) [Select]
  String key = getKey(seed);

in fact the table is replaced by a big string ....

you can measure RAM with this function:

Code: [Select]
int freeRam()
{
  extern int __heap_start, *__brkval;
  int v;
  return (int) &v - (__brkval == 0 ? (int) &__heap_start : (int) __brkval);
}

you can print its value before, inside and after encode

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart


You can only use a lot of memory if it is available. If I have  a sketch that uses 1950 bytes of RAM I cannot use CIFRA anymore as it uses e.g. 250 bytes of RAM.

The less RAM a library uses the more RAM is available for other functionality.

Similar reason you can make about performance. All CPU cycles used by communication cannot be used by measurements or math.

And yes increasing performance while decreasing memory load is definitely quite a challenge, so often these two are interchanged. If you want speed it costs more memory, if you want less memory usage the performance often drops. A similar trade off is there with speed and accuracy e.g. from sensors or a basic function like analogRead().


Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart

That's true for most encryptions, if you know how it is done it becomes easier to break.

cifra is a variation on Ceasarian (IIRC) code in which char's are replaced by the same char over and over again. In your version there are multiple conversion tables but with a frequency analysis one can probably break it. That said, it does not make the lib without value, in cases where simple encryption is needed.





Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

kowalski

#7
Jul 29, 2013, 02:30 am Last Edit: Jul 29, 2013, 02:31 am by kowalski Reason: 1
Great idea!

Thought I'd add something like this to the Cosa IOStream::Filter class. Did some prototyping in Linux first. The table can be removed. Below is two small programs I tested. The key is generated with random() and a seed. This should of cause be a parameter.

First the encoder.
Code: [Select]

#include <stdio.h>
#include <stdlib.h>

#define KEY_MAX 32

int main(int argc, char* argv[])
{
 char key[KEY_MAX];
 int nr;
 int c;

 // srandom(atoi(argv[1]));
 srandom(0x34893620);
 for (int i = 0; i < sizeof(key); i++) key[i] = random();
 nr = 0;
 while ((c = getchar()) != EOF) {
   c = (c + key[nr]) & 0xff;
   putchar(c);
   nr = (nr + 1) % sizeof(key);
 }
 return (0);
}


And then the decoder:
Code: [Select]

#include <stdio.h>
#include <stdlib.h>

#define KEY_MAX 32

int main(int argc, char* argv[])
{
 char key[KEY_MAX];
 int nr;
 int c;

 // srandom(atoi(argv[1]));
 srandom(0x34893620);
 for (int i = 0; i < sizeof(key); i++) key[i] = random();
 nr = 0;
 while ((c = getchar()) != EOF) {
   putchar(c - key[nr]);
   nr = (nr + 1) % sizeof(key);
 }
 return (0);
}

The algorithm is easily repackaged for strings, buffers, etc, as it is a simple one-to-one character mapping and can be made very**3 fast if needed. Using the full number range of char for the key and a large key (32+ length) gives a much better spread of the frequency of characters. I tested 32, 64 and 128 key length on a very large file with zip and checked the inflate numbers. The original file was inflated by 90% while the 128 key file could only be inflated to 30%. The character frequency histogram was very flat as expected.

NB: The seed method of generating the key is only an example. There are other methods. This is the lazy version ;-)

Cheers!

References:
1. http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher
2. https://chrome.google.com/webstore/detail/vigen%C3%A8re-cipher/jefmgpafeddooefhpnhccodndbcpbmhj
3. https://github.com/mikaelpatel/Cosa/blob/master/cores/cosa/Cosa/IOStream.hh

kowalski

#8
Jul 29, 2013, 11:57 am Last Edit: Jul 29, 2013, 09:26 pm by kowalski Reason: 1
Great inspiration!



The rewrite of my Linux test program became a template class in Cosa with support of Vigenere's autokey cipher (see links below). Using a template allows performance tuning down to 1475 ns per byte encoding/decoding (this includes reading the byte from program memory and a "checksum").

The memory requirement for the key table (the Vigenere class instance) is the size of the key plus 3 bytes (35 bytes for 32 byte key).

Cheers!

Links:
1. http://dl.dropboxusercontent.com/u/993383/Cosa/doc/html/db/da3/classVigenere.html
2. https://github.com/mikaelpatel/Cosa/blob/master/cores/cosa/Cosa/Crypto/Vigenere.hh

pito

This cipher is unbreakable if
a) the keyword is as long as the encrypted text
b) you always changes the keyword with a new text
:)

robtillaart

but the problem becomes how ALICE is going to share the continuous changing key with the receiver BOB.
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

pito

Quote
but the problem becomes how ALICE is going to share the continuous changing key with the receiver BOB.

Alice and Bob may share it through quantum entanglement..

Go Up