A few years ago I reinvented Naor and Shamir's visual one-time pad system, although I didn't get all the way to their k-of-n secret sharing scheme. The interesting thing about this scheme is that it allows you to decrypt the image by placing the key on top of the ciphertext and looking at it --- no further computation is needed.
It occurred to me that it was possible to extend the scheme to grayscale and thus make it easier to coregister the two images properly --- by making the pixels bigger --- without losing perfect security. I think a bunch of other people also have discovered this, but I don't know which ones yet. Here's an insecure proof-of-concept. It's necessary for perfect security that the random numbers have enough resolution to erase any trace of the original numbers from the encrypted image. Quantizing the original numbers to 8 bits would allow you to get by with 8 bits of randomness per pixel. It's also necessary to use real randomness, not a PRNG like random.random(). I wrote this on Bea's laptop, which doesn't have PIL, so I coded an ad-hoc BMP file reader for the front end. #!/usr/bin/python # Read a BMP file and turn it into PostScript of multiple pages that # contain the image encrypted. import sys, random, struct def decode_bmp_header(header): "Decode the header of a 24-bit BMP file." # here's the entry from /etc/magic I mean /usr/share/file/magic # # PC bitmaps (OS/2, Windoze BMP files) (Greg Roelofs, [EMAIL PROTECTED]) # 0 string BM PC bitmap data # >14 leshort 12 \b, OS/2 1.x format # >>18 leshort x \b, %d x # >>20 leshort x %d # >14 leshort 64 \b, OS/2 2.x format # >>18 leshort x \b, %d x # >>20 leshort x %d # >14 leshort 40 \b, Windows 3.x format # >>18 lelong x \b, %d x # >>22 lelong x %d x # >>28 leshort x %d # I think that means that at byte 14 there is a little-endian # short 40, at byte 18 there is a little-endian long for width, at # byte 22 there is a little-endian long for height, and at byte 28 # there is a little-endian short for depth. # On a particular 333-pixel-wide, 500-pixel-high, 24-bit BMP, I get: # PC bitmap data, Windows 3.x format, 333 x 500 x 24 (version,) = struct.unpack('<h', header[14:16]) assert version == 40, version (width, height) = struct.unpack('<ll', header[18:26]) (depth,) = struct.unpack('<h', header[28:30]) assert depth == 24, depth return width, height def read_bmp(fname): """Return the contents of a 24-bit BMP file as nested Python lists. Actually takes the average of the R, G, and B components, rather than returning them separately. """ infile = file(fname) # my sample image has a 56-byte header; I hope that's true of all BMPsxs header = infile.read(56) width, height = decode_bmp_header(header) rv = [] for ii in range(height): row = [] for jj in range(width): pix = infile.read(3) # assume 24-bit BMP rgb = [ord(c) for c in pix] avg = float(sum(rgb)) / (255*3) row.append(avg) rowbytes = width * 3 padbytes = 4 - (rowbytes % 4) if padbytes == 4: padbytes = 0 infile.read(padbytes) rv.append(row) return rv return [[float(ii)/width for ii in range(width)]] * height def print_postscript(image): "Obsolete routine for testing --- prints a graycale PostScript image." print """%! % total dumb-ass PostScript to draw an image pixel by pixel /pix { setgray gsave 0 1 rlineto 1 0 rlineto 0 -1 rlineto closepath fill grestore 1 0 rmoveto } bind def /row { grestore 0 1 rmoveto gsave } bind def 10 10 translate 1.5 dup scale 0 0 moveto gsave """ for row in image: for pixel in row: print "%f pix" % pixel print "row" print "grestore showpage" def make_pad(image, randomsource): # XXX note that this is not cryptographically secure without using # a cryptographically secure source of random numbers return [[randomsource() for pixel in row] for row in image] def pad_image(image, pad): return [[(0.5 - image[ii][jj] * 0.5 + pad[ii][jj]) % 1 for jj in range(len(image[0]))] for ii in range(len(image))] def print_postscript_boxy(images): """Prints the images given on top of each other in an obscured format. Each number gives the horizontal offset to provide to the empty part of a half-filled square. Thus overlaying two images will show the absolute difference of their pixels mod 1, as long as it does not exceed 0.5. """ width = len(images[0][0]) height = len(images[0]) maxscalex = 8.0 * 72 / width maxscaley = 10.5 * 72 / height scale = max(maxscalex, maxscaley) print """%! % Draw half-filled boxes for pixels with the fill being a vertical % half of the box, but rotated to the right by a specified amount. /pbox { dup 0.5 lt { % draw two black boxes gsave dup 0 rlineto 0 1 rlineto dup neg 0 rlineto closepath fill grestore gsave dup 0 rmoveto 0.5 0 rmoveto dup 0.5 exch sub dup 0 rlineto 0 1 rlineto neg 0 rlineto closepath fill grestore } { % else draw one black box gsave dup 0.5 sub 0 rmoveto 0.5 0 rlineto 0 1 rlineto -0.5 0 rlineto closepath fill grestore } ifelse pop 1 0 rmoveto } bind def /row { grestore 0 1 rmoveto gsave } bind def 18 dup translate """ print "%f dup scale" % scale for image in images: print "0 0 moveto gsave" for row in image: for pixel in row: print "%f pbox" % pixel print "row" print "grestore" print "showpage" if __name__ == '__main__': image = read_bmp(sys.argv[1]) pad = make_pad(image, random.random) padded = pad_image(image, pad) print_postscript_boxy([pad]) print_postscript_boxy([padded]) #print_postscript_boxy([pad, padded])