Register
It is currently Wed Dec 17, 2014 8:56 pm

ESE -- Extreme Simple Encrypter


All times are UTC - 6 hours


Post new topic Reply to topic  [ 4 posts ] 
Author Message
 PostPosted: Sun Sep 05, 2010 7:30 am   
User avatar

Joined: Sun Jun 27, 2010 12:57 am
Posts: 192
Here's some piece of code implementing an asynchronous (public/private key) encryption algorithm, based on Merkle–Hellman knapsack cryptosystem. It's in the early stages, so any feedback is appreciated.
This encryption algorithm has long since been cracked, so don't go encode anything worthwhile with it :)
It requires gawk.


Code:
#!/bin/bash

PID=$$
SELF=$(basename "$0")
VERSION="0.3"

function usage() {
  echo
  echo "ESE -- Extreme Simple Encrypter; v${VERSION} by Patsie"
  echo
  echo "To generate a public/private key-pair: $SELF -k [3..11]"
  echo "To encode a message: $SELF -e <public key>"
  echo "To decode a message: $SELF -d <private key>"
  echo
  echo "Example:"
  echo " \$> $SELF -k 7"
  echo " private = 0157:00ad:0055:002c:0015:000b:0007:1183:0683"
  echo " public  = 0988:05c7:0aa2:0654:0e2a:0195:0a8f"
  echo
  echo " \$> echo Hello | $SELF -e 0988:05c7:0aa2:0654:0e2a:0195:0a8f"
  echo " 13f1:1b85:24d4:1947:1b73:24e7"
  echo
  echo " \$> echo 13f1:1b85:24d4:1947:1b73:24e7 | $SELF -d 0157:00ad:0055:002c:0015:000b:0007:1183:0683"
  echo " Hello"
  echo
  exit 1;
}

## do options
[ $# -lt 1 ] && usage
while [ -n "$*" ]; do
  opt="$1"; shift;
  case "$opt" in
    "-k")  mode="keygen";  len="$1"; shift ;;
    "-e")  mode="encode";  key="$1"; shift ;;
    "-d")  mode="decode";  key="$1"; shift ;;
    *) usage ;;
  esac
done


/usr/bin/gawk -v mode="$mode" -v key="$key" -v keylen="$len" '
  ##
  ## print array contents in 32bit hexadecimal
  ##
  function print_hex(name, arr) {
    len = arr[0];
    printf("%s%04x", name?name" = ":"", arr[1]);
    for (i=2; i<=len; i++) printf(":%04x", arr[i]);
    printf("\n");
  }

  ##
  ## split hexadecimal input into decimal array
  ##
  function splitx(str, arrDec, sep) {
    # split input
    myTmp[0] = split(str, myTmp, sep);

    # convert (back) to decimal
    for (i=1; i<=myTmp[0]; i++)
      arrDec[i] = strtonum("0x"myTmp[i]);
    arrDec[0] = myTmp[0];

    # return number of elements
    return(arrDec[0]);
  }

  ##
  ## return single bit at position X from character stream
  ##
  function bitstream(str, pos) {
    c = ORD[substr(str,int(pos/8)+1,1)];
    return(int(c/(2^(7-(pos%8)))%2));
  }

  ##
  ## calculate mutiplicative inverse mod (Extended Euclidean Algorithm)
  ##
  function inverse_mod(x, mod) {
    a=x; b=mod;
    x1=0; x2=1;

    while (b > 0) {
      q=int(a/b);
      tmp=b; b=a%b; a=tmp;
      tmp=x1; x1=x2-(q*x1); x2=tmp;
    }
    while (x2<0) x2+=mod;
    return(x2);
  }

  ##
  ## generate public/private key-pair
  ##
  function keygen(len, private, public) {
    ## clear keys
    delete(private);
    delete(public);

    ## generate super-increasing set for private key
    sum = 0;
    for (i=len; i>0; i--)
      sum += private[i]=(sum+int(rand()*6)+2);

    ## get prime for modulo calculus and random multiplier
    for (i=1; i<=NPRIMES; i++)
      if ((prime=PRIMES[i]) > sum) break;
    multi = int(rand()*(prime-1))+1;      # rand()*(prime-2)+1 ??

    ## store prime and multiplier in private key
    if (prime < sum) { printf("FATAL: keygen(): prime(%d) < sum(%d)\n", prime, sum); exit 1; }
    private[len+1] = prime;
    private[len+2] = multi;
    private[0] = len+2;

    ## generate public key from private key
    for (i=len; i>0; i--)
      public[i]=(private[i]*multi)%prime;
    public[0] = len;
  }

  ##
  ## encode a string according to a (public)key and put result in encrypted array
  ##
  function encode(key, str, arr) {
    delete(arr);
    alen = 0;
    slen = length(str);
    klen = key[0];

    bitpos = 0;

    ## repeat for all characters in str
    while (bitpos < slen*8) {
      alen++;
      encoded = 0;

      ## encode each bit
      for (b=0; b<klen; b++)
        encoded += bitstream(str, bitpos+b) * key[b+1];

      ## store encrypted value in array
      arr[alen] = encoded;
      bitpos += klen;
    }

    # return encrypted array length
    arr[0] = alen;
  }

  ##
  ## decode an encrypted array back into a string according to a (private)key
  ##
  function decode(key, arr) {
    str="";
    blen = 0;
    alen = arr[0];
    klen = key[0]-2;
    decoded = 0;
   
    ## generate modulo inverse multiplier
    r1 = inverse_mod(key[klen+2], key[klen+1]);

    ## decode each encoded array entry
    for (i=1; i<=alen; i++) {

      ## calculate reverse value
      n = (arr[i]*r1)%key[klen+1];

      ## decode all bits in reverse value
      for (b=1; b<=klen; b++) {
        if (n >= key[b]) {
          decoded += 2^(7-blen);
          n -= key[b];
        }

        ## convert 8 decoded bits to character
        blen++;
        if (blen == 8) {
          if (decoded > 0)
            str = sprintf("%s%c", str, decoded);
          decoded = 0;
          blen = 0;
        }
      }

      ## sanity checksum, reverse value should be empty after full decode
      if (n != 0)
        printf("decode(): Invalid checksum (%d!=0)\n", n);
    }

    return(str);
  }

BEGIN {
  srand();
  NPRIMES = split("4483,4799,4903,4933,5351,5779,5857,5867,5881,6659,6689,6971,7001,7151,7213,7753,7873,8707,8831,8893,8951,9277,9319,9467,9521,9533,9547,9551,9601,9613,9623,9629,9643,9649,9677,9679,9697,9719", PRIMES, ",");

  for (i=0; i<256; i++) ORD[sprintf("%c",i)] = i;

  ## generate key-pair and exit
  if (mode == "keygen") {
    keygen(keylen, private, public);
    print_hex("private", private);
    print_hex("public ", public);
    exit 0;
  }

  ## parse public/private key
  if (mode == "encode") public[0] = splitx(key, public, ":");
  if (mode == "decode") private[0] = splitx(key, private, ":");
}

{
  ## encode/decode line
  if (mode == "encode") { encode(public, $0, myArr); print_hex("", myArr); }
  if (mode == "decode") { myArr[0] = splitx($0, myArr, ":"); printf("%s\n", decode(private, myArr)); }
}'


Top
 Profile  
 PostPosted: Sun Sep 05, 2010 8:42 pm   
Site Admin
User avatar

Joined: Sun May 15, 2005 9:36 pm
Posts: 673
Location: Des Moines, Iowa
I think this encryption algorithm has been cracked before ?
http://ieeexplore.ieee.org/search/frees ... er=4568386

I'm assuming this is for use when the computer in use doesn't have gpg available and your not allowed to install it ?

Interesting though, I didn't trace all the code from beginning to end, but it's definitely interesting.


Top
 Profile WWW  
 PostPosted: Sun Sep 05, 2010 10:25 pm   
User avatar

Joined: Sun Jun 27, 2010 12:57 am
Posts: 192
Yeah, like I said in my opening post, this has been cracked. It's not meant to be a secure encryption. It was more of a brain exercise. It can be used for short timespan, low importance messages.


Top
 Profile  
 PostPosted: Mon Sep 06, 2010 7:21 pm   
Site Admin
User avatar

Joined: Sun May 15, 2005 9:36 pm
Posts: 673
Location: Des Moines, Iowa
Ack, sorry, I missed that.......... b-(

Some cool code though... ;)


Top
 Profile WWW  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Jump to:  
cron


BashScripts | Promote Your Page Too
Powered by phpBB © 2011 phpBB Group
© 2003 - 2011 USA LINUX USERS GROUP