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

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.

# 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)
        rowbytes = width * 3
        padbytes = 4 - (rowbytes % 4)
        if padbytes == 4: padbytes = 0
    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, padded])

Reply via email to