"
Team:Davidson-Missouri Western/Hash Functions and Biological Systems
From 2008.igem.org
(Difference between revisions)
| Line 38: | Line 38: | ||
<br> | <br> | ||
| - | * | + | ==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 | ||
| + | [[Image:linearmod.jpg|500px]] | ||
Latest revision as of 02:22, 30 October 2008
| 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.
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:
| 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
