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

From 2008.igem.org

(Difference between revisions)

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:

**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

@@ Line 1: / Line 1: @@
-'''XOR Logic Gate'''
+{| style="color:#1b2c8a;background-color:#0c6;" cellpadding="3" cellspacing="1" border="1" bordercolor="#fff" width="62%" align="center"
+!align="center"|[[Team:Davidson-Missouri_Western|Home]]
+!align="center"|[[Team:Davidson-Missouri_Western/Team|The Team]]
+!align="center"|[[Team:Davidson-Missouri_Western/Project|''E. nigma'' Project]]
+!align="center"|[[Team:Davidson-Missouri_Western/New_Parts_Contributed_to_the_Registry|Parts Submitted to the Registry]]
+!align="center"|[[Team:Davidson-Missouri_Western/Notebook|Notebook]]
+|}
-[[Image:xorslide.jpg]]
+==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.
+[[Image:convertmess.jpg|400px]]
+==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:
+{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
+|+ '''Exclusive Disjunction'''
+|- style="background:paleturquoise"
+! style="width:15%" | p
+! style="width:15%" | q
+! style="width:15%" | p ⊕ q
+|-
+| T || T || F
+|-
+| T || F || T
+|-
+| F || T || T
+|-
+| F || F || F
+|}
+<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]]