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])
