pgp-in-50-lines-of-perl? (Re: The Pure Crypto Project's Hash Function)

[Adam Back]

On Mon, May 05, 2003 at 12:07:53AM -0700, Bill Stewart wrote:
> > > There is also a RSA key generator (including prime generation) by
> > > Steve Reid in 13 lines.  I guess you could probably get a basic PGP
> > > compatible implementation of encryptions, signature and keygen in one
> > > page of perl/dc etc. ie 60 lines perhaps less.  I mean we have RSA in
> > > 2 lines, md5 in 8 lines, key gen in 13 lines; you'd need IDEA which no
> > > one has implemented in compacted perl, but we have
> > > 2+8+13+IDEA+formatting IDEA has no s-boxes or magic values or
> > > anything, so could probably be quite compact and perl is good at
> > > formatting.
> >
> >Is there anything I can do to make you come forward with at least
> >some of this to look at?
> 
> It's all sitting on http://cypherspace.org/~adam/rsa/ ,

Another good source of parts (though not yet optimized for size) is
pgpacket which can parse pretty much any openPGP packets and tell you
about them: http://web.meson.org/pgpacket/

It also includes base64 encoded which is another required component.

I'm not sure I still have the PGP2.x compatible signature in n-lines
of code; I was talking with Dan Farmer who was thinking of literally
using it (maybe for satan signing I forget).

But I did start working on this once, and here are the parts (last
file modification Oct 2001, but probably older as they all have same
stamp, so probably correspond to transfer from old machine).  So this
is a bunch of not previously released small stuff:

Actually I forgot I had written an IDEA in perl -- I guess I never put
it on the web because it's PGP CFB style IDEA, and I never got around
to making a pure IDEA version.

This is PGP compatible IDEA in 7 lines (ie CFB mode including the 2
byte checkdigits and zero IV and 8 byte random plaintext prefix).

#!/usr/bin/perl -s0777
$n=($m=4**8)+1;sub M{$_[0]%=$m}sub N{$_[0]=(($z=($K[$o++]||$m)*($_[0]||$m))-$n*
int$z/$n)%$m}sub A{N$A;M$B+=$K[$o++];M$C+=$K[$o++];N$D}$_=unpack("B*",pack H32,
$k)x9;@K=unpack n52,pack"B*"x7,/(.{128}).{25}/g;sub E{($A,$B,$C,$D,$o)=unpack
n4,$_[0];map{A;$c=$C;$C^=$A;$b=$B;$B^=$D;M$B+=N$C;M$C+=N$B;$A^=$B;$D^=$C;$B^=$c
;$C^=$b}1..8;A$B^=$C^=$B^=$C;pack n4,$A,$B,$C,$D}$_=<>;$d?(s/..(.{8})//,$i=$1):
($i=pack(H16,$i,$j=substr$i,6,2),print($i^=E,substr$j^=E($i),0,2),$i=~s/../$'$j
/);print substr$d?E($i)^($i=$&):($i=E($i)^$&),0,length$&while/.{1,8}/gs

Usage:

% echo hello world > msg
% pgpidea -e -i=0123456701234567 -k=0123456789abcdef0123456789abcdef < msg > msg.idea
% pgpidea -d -k=0123456789abcdef0123456789abcdef < msg.idea
hello world

(the i is the random plaintext prefix mnemonic i for IV as it is
effectively an encrypted IV).

(Actually I'm finding if you specify the -i flag it doesn't decrypt --
must've introduced a bug when I was shortening last -- no time to
figure that out now).

And here is some relatively compacted PGP keyring database code which
reads a PGP2.x compatible keyring and outputs the public key and
private key:

#!/usr/bin/perl -s0777
sub o{open P,"$ENV{'PGPPATH'}/@{_}ring.pgp";<P>}$g=o pub;$h=o sec;$u=lc$u;$w=(
$u=~s/^0x//);sub p{$_=$_[0];s/.//;$t=(ord$&&60)>>2;$l=2**(ord$&&3)&7;s/.{$l}//
s;$l=unpack N,"\0"x(4-$l).$&;s/.{$l}//s;$_[0]=$_;$&}sub r{$_[0]=~s/..//s;$l=
int(.9+unpack(n,$&)/8);$_[0]=~s/.{$l}//s;unpack"H*",$&}sub k{$f=$_[0];while($f
){$_=p$f;if($t==6||$t==5){s/.{8}//s;$n=r$_;$pe=r$_;$r=$_;$_=p$f;$_=p$f while$t
==12;$/=substr$n,-8;if($v){print"0x$/"}}if($t==13){$v?print"\t$_\n":return if(
$w&&$/eq$u||index(lc$_,$u)>=0){return}}}}
 
k$h;
print "sec 0x$/ $_\n";
print "seckey: ",unpack("H*",$r),"\n";
 
k$g;
print "pub 0x$/ $_\n";

the stuff at the end just demonstrates what the function achieves.

It can decrypt private keys, prompting for the password which it gives
to the (external) md5 in perl, and then decrypts the private key
parameters using the (external) pgpidea script above :-)

Usage

# lookup by keyID
pgpkey -u=0x01234567
# lookup by userID
pgpkey -u=adam at cypherspace.org
# display keys in the database
pgpkey -v

(actually I'm not sure if this was fully debugged, I don't recall; but
it can't be far off as the external components pgpidea and md5 are
there and working.)

I did once have some compacted base64 code based on uuencode mode of
perl's pack function, think I lost it but it should be easy to
recreate.  (Uuencode is the same as base64 but with a different
alphabet; the trick is to use pack("u*"). and then y/// to transform
the differences).

btw If anyone is interested to work on this I have more commented
versions which I could share or get nudged into putting on the web.

btw#2 Ralf recently sent me some improvements to the rc4 in perl, and
then I got tinkering and found another 32 bytes so it's now quite a
lot smaller, if that motivates anyone to find further improvements (I
ran out of ideas for now):

#!/usr/bin/perl -0777
@k=map hex,pop=~/../g;@s[$w++,$z]=@s[$z=$k[$w%@k]+$_+$z&
255,$w]for at s=0..255;@s[$y,$x]=@s[++$x,$y=$s[$x%=@s]+$y&
255],print chr($_^$s[$s[$x]+$s[$y]&255])for unpack"C*",<>

the previous version was:

#!/usr/bin/perl -0777
@k=unpack'C*',pack'H*',shift;for(@t=@s=0..255){($y+=$k[$_%@k]+$s[$x=
$_])%=256;&S}$x=$y=0;for(unpack'C*',<>){($y+=$s[($x+=1)%=256])%=256;
&S;print chr($_^=$s[($s[$x]+$s[$y])%256])}sub S{@s[$x,$y]=@s[$y,$x]}

Fun!

Adam

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com