Team:Davidson-Missouri Western/Hash Functions and Biological Systems

From 2008.igem.org

Revision as of 02:22, 30 October 2008 by Laheyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Home The Team E. nigma Project Parts Submitted to the Registry Notebook

Binary Encoding

The input message must be converted to binary before computation begins. We used an [http://www.asciitable.com/ ascii table] to convert each letter in message to a decimal number, which is then converted to binary as shown in the following examples.

Convertmess.jpg


XOR logic

We used XOR logic to build our cryptographic hash function with E. coli. XOR, or eXclusive OR, is a logic gate that produces a value of true if and only if exactly one of its inputs is true.

The truth table for p XOR q (also written as p + q, p ⊕ q, or p ≠ q) is as follows:

Exclusive Disjunction
p q p ⊕ q
T T F
T F T
F T T
F F F


Computing the Hash Value

The diagram illustrates how a simple hash function can be implemented in a Petri dish with E. coli. This simple linear model is the basis of all our other models

  • The gold-colored ovals represent bacterial colonies spotted on the plate.
  • The input message "CAB" is converted to a binary string
    • Each digit in the string is encoded by the presence (1) or absence (0) of a signal molecule.
    • The first binary digit in the string is used as the "key" at the top of the linear model.
    • Remaining digits are shown in the blue drops to the left of the colonies.
  • Each colony computes an XOR of two inputs: one from the colony above, and one from the input digit to the left of the colony
  • The hash value is the output of the final colony

Linearmod.jpg