Kryptografia molekularna

Kryptografia molekularna

Krzysztof Ma

kowiak

Doradztwo Gospodarcze DGA S.A., Politechnika Poznańska

www.kryptografia.com

Celem referatu jest przybli

enie innej, alternatywnej metody ochrony danych.

Niekonwencjonalne podej

cie, wykorzystuj

ce cz

steczki DNA, umo

liwia

wykonywanie najwa

niejszych operacji wykorzystywanych w ochronie danych

takich jak: szyfrowanie, ukrywanie danych (steganografia), tworzenie skrótu,
kryptoanaliza oraz identyfikacja osób. W referacie przedstawione b

podstawowe poj

cia zwi

zane z biologi

(budowa cz

steczki DNA, ła

cuchowa

reakcja polimerazy, sekwencjonowanie) oraz bioinformatyk

(komputer DNA i

jego porównanie z komputerami tradycyjnymi, wykorzystywanie DNA i RNA do
rozwi

zywania problemów obliczeniowych). Omówione b

w skrócie

sposoby wykorzystywania cz

steczek DNA w ochronie danych oraz dokładnie

przedstawione zostan

przykładowe metody kryptografii i steganografii z

wykorzystaniem cz

steczek DNA.

1. Budowa cz

steczek DNA

Wszystkie organizmy

ywe maj

podobn

molekularn

budow

biochemiczn

Składaj

z tych samych molekuł: białek i kwasów nukleinowych. Kwasy

nukleinowe koduj

informacj

genetyczn

potrzebn

do wytwarzania białek i

przekazania tych reguł nast

pnym pokoleniom.

Wyró

niamy dwa rodzaje kwasów nukleinowych:

DNA – deoksyrybonukleinowy (deoxyribonucleic acid),

RNA – rybonukleinowy (ribonucleic acid).

Zasad

budowy DNA odkryli w 1953 roku:

J.D. Watson i F.H. Crick – model helisy – Nagroda Nobla,

M. Wilkins – Nagroda Nobla,

R.E. Franklin.

DNA jest dwuniciow

helis

składaj

z prostszych molekuł (nukleotydów).

Pojedynczy nukleotyd zbudowany jest z:

steczki cukru – deoksyrybozy (2’-deoxyribose), zawieraj

cej pi

ęć

atomów

gla, oznaczonych od 1’ do 5’.

jednej grupy fosforanowej,

zasady azotowej.

Molekuły DNA ró

zasadami azotowymi. To wła

nie zdefiniowana kolejno

ść

zasad zawartych w cz

steczkach DNA stanowi no

nik informacji genetycznych.

Wyró

nia si

cztery zasady azotowe: adenina A (adenine), guanina G (guanine),

cytozyna C (cytosine) oraz tymina T (tymine). Adenina i guanina to pochodne
puryny, natomiast cytozyna i tymina to pochodne pirymidyny.

Nukleotydy w zale

ci od wyst

puj

cych w nich zasad nazywamy:

deoksyadenylanem (z adenin

), deoksyguanylanem (z guanin

deoksycytydylanem (z cytozyn

) oraz deoksytymidylanem (z tymin

). Ła

cuch DNA

jest oligonukleotydem.

Podwójn

helis

DNA otrzymujemy dzi

ki wi

zaniom zasad komplementarnych

(wi

zania wodorowe, H-bond). Ze wzgl

du na budow

helisy, mo

liwe s

purynowo-

pirymidowe pary zasad. Jednym ze składników musi by

puryna, drugim za

piramidyna. Powstawanie par zasad (hybrydyzacja, parowanie) jest dodatkowo
ograniczone warunkami tworzenia si

wodorowych. Atomy wodoru w

zasadach zajmuj

dokładnie zdefiniowane poło

enie. Adenina nie mo

e tworzy

pary z cytozyn

, gdy

w jednej z pozycji wi

ążą

cych mogłyby znajdowa

dwa

wodory, natomiast w drugim brakowałoby wodoru (komplementarno

ść

zasad).

Podobnie guanina nie mo

e tworzy

pary z tymin

. Mo

liwe jest utworzenie

nast

puj

cych par: A-T (adenina-tymina) oraz G-C (guanina-cytozyna).

Pomi

dzy zasadami wyst

puj

zania wodorowe:

podwójne pomi

dzy A i T,

potrójne pomi

dzy G i C.

Rdze

DNA jest stały dla całej cz

steczki i składa si

z reszt deoksyrybozy

poł

czonych resztami fosforanowymi. Zasady purynowe i pirymidowe znajduj

wewn

trz ła

cucha, a fosforany i reszty deoksyrybozy – na zewn

trz helisy. Zasady

skr

cone wzgl

dem siebie pod k

tem 36˚. Zatem na całkowity skr

t helisy

przypada 10 nukleotydów w ka

dym ła

cuchu.

Ła

cuch DNA wykazuje polarno

ść

. Jeden z jego ko

ców ma grup

5’-OH, drugi

3’-OH. Przyjmuje si

e niezwi

zana grupa 5’-OH jest ulokowana w nukleotydzie

znajduj

cym si

po lewej stronie zapisu, natomiast grupa 3’-OH po prawej stronie.

Zasady zapisujemy, wi

c w kierunku 5’->3’.

Obie nici DNA maj

przeciwn

orientacj

- s

antyrównoległe. Znaj

c jeden ła

cuch,

na odtworzy

drugi poprzez operacj

odwrotnego dopełnienia (reverse

complementation).

5’ … TAGACTTAGGC … 3’

3’ … ATCTGAATCCG … 5’

Jest to podstawa mechanizmu replikacji DNA w komórkach. W procesie replikacji,
bior

udział enzymy, zwane polimerazami DNA, które w procesie tym czerpi

instrukcje od matrycowych ła

cuchów DNA.

Dwuniciowa helisa stabilizowana jest przez wi

zania wodorowe mi

dzy

komplementarnymi zasadami. Po ich zerwaniu dwa ła

cuchy DNA z łatwo

rozdzielaj

. Efekt ten mo

na uzyska

, przez ogrzewanie roztworu DNA, jego

zakwaszaniu albo alkalizacj

, powoduj

ce jonizacj

zasad tzw. denaturacj

. Proces

rozplatania dwuniciowej helisy nazywamy topnieniem. Temperatura topnienia zale

od ilo

ci odpowiednich par zasad. Musi by

ona wy

sza, gdy mamy wi

cej par G-C,

które s

stabilniejsze od par A-T.

1.1. Reakcja ła

cuchowa polimerazy (PCR – polymerase chain reaction)

Reakcja PCR opracowana została przez K.B. Mullisa i M. Smitha, którzy otrzymali za
to odkrycie Nagrod

Nobla w dziedzinie chemii w 1993 roku. Jest to reakcja

powielania (amplifikacji) okre

lonej sekwencji DNA. Reakcja PCR wykorzystuje

enzym (polimeraz

DNA), który jest katalizatorem syntezy pojedynczego ła

cucha

DNA. Polega ona na rozpleceniu podwójnego ła

cucha (etap denaturacji). Etap

anilingu: hybrydyzacja primera komplementarnego do ko

ca 5’ pojedynczego

ła

cucha DNA. Kolejny etap: polimeryzacja – do ko

ca 3’ primera zostanie

dobudowana komplementarna ni

DNA. W efekcie tych trzech etapów powstanie

dwuniciowa helisa. Poszczególne etapy zwi

zane s

ze zmian

temperatury,

dlatego w reakcji PCR wykorzystywana jest polimeraza odporna na wysok

temperatur

Jednokrotna reakcja podwaja liczb

kopii. Wielokrotne zastosowanie reakcji PCR

powoduje ekspotencjalny przyrost liczby kopii. Bł

dy w procesie powielania

wyst

puj

bardzo rzadko, mniej wi

cej raz na 10 miliardów zreplikowanych zasad.

1.2 Sekwencjonowanie

Metoda ta, wynaleziona przez naukowców ameryka

skich i brytyjskich w roku 1977,

polega na podziale cz

steczki DNA na fragmenty a nast

pnie na odczytaniu

sekwencji nukleotydów, z których składa si

ta cz

steczka.

Istnieje wiele metod sekwencjonowania. Przykładowe metody:

1. Elektroforeza DNA w

elu agarozowym – fragmenty ła

cuchów DNA

umieszczamy w 4 kieszonkach i poddajemy działaniu silnego pola
elektrycznego, na skutek czego fragmenty DNA migruj

elu w kierunku

elektrody dodatniej (DNA ma ładunek ujemny) z szybko

zale

od ich

wielko

ci i kształtu. Nast

pnie odczytujemy sekwencj

na podstawie

kolejno

ci pr

ąż

ków. Metoda nie jest pozbawiona bł

dów.

2. Sekwencjonowanie przez hybrydyzacj

– wykorzystujemy mo

liwo

ść

tworzenia helisy z pojedynczej nici. Chcemy odczyta

sekwencj

nukleotydów

pojedynczej nici o długo

ci n. Wprowadzamy j

do roztworu wraz z pełn

bibliotek

oligonukleotydów o długo

ci k (k<<n). Oligonukleotydy, które

wykrywamy na podstawie fluorescencji, przył

czaj

do ła

cucha. Po

przył

czeniu mo

emy na podstawie barwy przył

czonych oligonukleotydów

odczyta

szukan

sekwencj

ła

cucha. Bibliotek

nukleotydów mo

stworzy

na specjalnym chipie.

Bioinformatyka

(bioinformatics, biocomputing) zajmuje si

symulacjami

komputerowymi w biochemii i biologii molekularnej, tworzeniem i zarz

dzaniem

bazami danych, poszukiwaniem, wyci

ganiem, analiz

i interpretacj

informacji z

biologicznych baz danych, tworzeniem nowych algorytmów i metod statystycznych
do analizy danych biologicznych oraz innymi technikami informatycznymi
zwi

zanymi z naukami biologicznymi.

Informatyka DNA (DNA computing) okre

lana równie

jako informatyka

molekularna, jest now

alternatyw

dla równoległych systemów komputerowych. Jej

pocz

tek si

ga 1994 roku, kiedy to Leonard M. Adleman (współtwórca znanego

algorytmu szyfrowania asymetrycznego RSA) po raz pierwszy zademonstrował
mo

liwo

ść

wykorzystania cz

steczek molekularnych do rozwi

zywania problemów

matematycznych. Z u

yciem cz

steczek DNA rozwi

zał on siedmiowierzchołkowy

(14 dróg) problem poszukiwania

cie

ki Hamiltona.

cie

ka Hamiltona jest

cie

wychodz

z dowolnego, ustalonego wierzchołka

grafu i przechodz

przez wszystkie wierzchołki dokładnie jeden raz (przez

pojedyncz

kraw

e przej

ść

wielokrotnie).

cie

ka ko

czy si

w ustalonym

wierzchołku docelowym (w przypadku cyklu Hamiltona jest to ten sam wierzchołek,
w którym rozpocz

to poszukiwanie).

Algorytm Leonarda Adlemana dla grafu o n wierzchołkach:

Stwórz du

y zbiór losowych

cie

ek, przechodz

cych przez graf.

II)

Dla ka

dej

cie

ki sprawd

, czy:

a) zaczyna si

w wierzchołku pocz

tkowym i ko

czy w docelowym, je

eli

nie to usu

ze zbioru,

b) przechodzi dokładnie przez n wierzchołków, je

eli nie to usu

zbioru,

c) przechodzi dokładnie przez ka

dy wierzchołek, je

eli nie to usu

zbioru.

eli powstały zbiór zawiera elementy to istnieje szukana

cie

Hamiltona, w przeciwnym razie (zbiór jest pusty)

cie

ka nie istnieje.

Problem ten zaliczamy do grupy problemów NP-zupełnych, których nie mo

rozwi

w czasie wielomianowym. Adleman rozwi

zał ten problem generuj

wszystkie mo

liwe kombinacje jako odr

bne ła

cuchy DNA. Dla siedmiu

wierzchołków rozwi

zanie jest trywialne i mo

na je szybko otrzyma

, stosuj

normalne komputery lub obliczaj

c r

cznie. Przykład ten ilustruje jednak potencjalne

liwo

ci komputerów i informatyki DNA.

Inne do

wiadczenie przeprowadzone w Mount Sinai School of Medicine w Nowym

Yorku pokazuje mo

liwo

ść

wykonywania operacji dodawania liczb binarnych

reprezentowanych przez ła

cuchy DNA. Powstał równie

komputer DNA, z którym

na zagra

w gr

„kółko i krzy

yk”.

W 2000 w Princeton przedstawiono mo

liwo

ść

zastosowania cz

steczek RNA do

rozwi

zywania problemów (problem skoczków szachowych na szachownicy o

wielko

ci 3x3) oraz budowy komputerów molekularnych.

2. Komputer DNA

Komputer DNA (molekularny) jest to zbiór specjalnie wyselekcjonowanych
ła

cuchów DNA, których kombinacja spowoduje rozwi

zanie postawionego

problemu. Nadziej

pokładan

w komputerach DNA jest ich wysoki stopie

równoległo

ci, co potencjalnie powinno umo

liwi

rozwi

zanie problemów

wymagaj

cych wielu oblicze

poprzez obliczenia równoległe.

W 1973 roku Charles Benett zaproponował model programowalnego komputera
molekularnego zdolnego do realizacji dowolnego algorytmu. W praktyce pierwsze
komputery powstały w 2001 roku. Autorami jednego z nich s

naukowcy z Instytutu

Weizmanna w Rehovot, którzy wykorzystali w swoich do

wiadczeniach cz

steczki

DNA, które pełni

zarówno rol

„oprogramowania”, sygnału wej

cia-wyj

cia, jak

równie

dostarczaj

potrzebnej energii. W roku 2003 komputer ten został

udoskonalony i osi

gał pr

dko

ść

reakcji molekularnych 330 TFLOPS w obj

ci 5

mililitrów (mała ły

eczka płynu). W komputerze tym rol

sprz

tu pełni

enzymy

restrykcyjne, które rozpoznaj

le okre

lone sekwencje DNA i w ich obr

bie

przecinaj

steczk

Równie

w Polsce trwaj

badania nad stworzeniem komputera molekularnego. W

roku 2002 we Wrocławiu powstała tzw. Grupa Inicjatywna Konstrukcji Prototypu
Opartego na DNA.

2.1. Komputery DNA a komputery tradycyjne

Porównanie komputerów tradycyjnych i komputerów zbudowanych z cz

steczek

DNA jest bardzo trudne i mo

e doprowadzi

w wielu sytuacjach do rozbie

nych

wyników. Poni

sze dane nale

y zatem traktowa

jedynie jako dane przybli

one.

DNA jako no

nik informacji – pojemno

ść

pami

ci biologicznej jest znacznie wi

ksza

stosowanych dzisiaj no

ników. Małe rozmiary DNA sprawiaj

e w obj

ci 1

mie

ci si

10 mld MB informacji – 10 PB (zakładaj

e jedna para

nukleotydów stanowi jeden bit informacji – 0 lub 1). Jeden gram DNA zawiera 10

zasad DNA, co odpowiada 10

TB danych. Kilka gramów DNA mo

e kodowa

wszystkie informacje dost

pne na ziemi.

DNA jako superkomputer. Zakładaj

e przoduj

ce komputery umo

liwiaj

działania z pr

dko

100 MIPS (milion instrukcji na sekund

), ła

cuchy DNA

działaj

z pr

dko

ponad

10 razy szybsz

Komputery DNA zapewniaj

y stopie

równoległo

ci przetwarzania. W jednej

kropli roztworu wodnego mo

e znajdowa

ponad bilion molekularnych

procesorów, wykonuj

cych miliard operacji na sekund

Komputery DNA nie potrzebuj

zasilania elektrycznego i s

wysoce

energooszcz

dne.

Na podstawie tych informacji wida

e komputery DNA stanowi

ciekaw

alternatyw

dla komputerów stacjonarnych.

2.2. Kodowanie DNA a kodowanie binarne

W przypadku kodowania binarnego operujemy dwoma bitami 0 i 1. W przypadku
kodowania DNA mamy mo

liwo

ść

skorzystania z 4 nukleotydów A,T,G,C.

W zale

ci, ile znaków b

dziemy chcieli zakodowa

, taki długi b

dzie ci

nukleotydów przypadaj

cy na ka

dy znak. W przypadku, gdy chcemy zakodowa

ró

ne znaki potrzebujemy ci

gu składaj

cego si

z 3 nukleotydów.

emy równie

traktowa

A i T jako 0 a G i C jako 1. Korzystaj

c z alfabetu ASCII

znak A mo

na zapisa

jako 65

=1000001

=GTTATAC. Nie musimy tworzy

specjalnego alfabetu. W tym przypadku nie wykorzystujemy czterech zasad do
kodowania tylko dwie.

Przy budowie alfabetu nale

y stosowa

metody charakterystyczne dla szyfrów

homofonicznych (najcz

ęś

ciej wyst

puj

ce litery kodowane s

za pomoc

kilku

czwórek). Zapobiega to sytuacji, w której charakterystyczny kawałek tekstu, mógłby
by

traktowany przez kryptoanalityka jako nowy primer. Dzi

ki temu mógłby on

otrzyma

ęść

szukanego tekstu. Inn

liwo

jest zastosowanie kompresji lub

innej metody do zmiany układu liter w tek

cie jawnym przed jego zamian

na ci

nukleotydów. Metoda ta podobnie jak klucz nie mo

e zosta

ujawniona.

3. DNA a ochrona danych

Biotechnologia znajduje swoje zastosowanie równie

w zagadnieniach zwi

zanych z

ochron

danych.

DNA mo

e by

wykorzystywane w:

kryptografii – stosowany algorytmy jednorazowy (one-time-pad) z
wykorzystaniem operacji podstawienia lub XOR,

steganografii – bezpieczne ukrycie wiadomo

ci a nast

pnie jej odtworzenie

dzi

ki posiadanej wiedzy o kluczu,

tworzeniu molekularnej sumy kontrolnej z wykorzystaniem obrazów

elowych,

jako odpowiednik skrótu (funkcji haszuj

cej), wykorzystany do znakowania

przedmiotów,

systemach identyfikacji osób,

kryptoanalizie – do łamania konwencjonalnych algorytmów symetrycznych
(np.DES) oraz asymetrycznych.

3.1. Kryptografia DNA

Algorytm jednorazowy (One-time-pad)

Tekst jawny jest szyfrowany przy u

yciu cz

steczek DNA za pomoc

algorytmu

jednorazowego, który po spełnieniu trzech podstawowych warunków jest
algorytmem zapewniaj

cym bezwzgl

dne bezpiecze

stwo. Trzy podstawowe

warunki, które musi spełnia

ła

cuch DNA stanowi

cy klucz:

musi by

przynajmniej tak długi jak szyfrowany tekst (przy du

upakowaniu danych w cz

steczkach DNA nie stanowi to wi

kszego

problemu),

musi by

losowy,

e by

yty tylko jeden raz.

Zanim zaczniemy szyfrowanie za pomoc

tej metody musimy stworzy

długi ła

cuch

DNA (klucz) zbudowany z losowo wybranych krótkich sekwencji oligonukleotydów.
Ten ła

cuch stanowi podstaw

naszej metody. B

dzie u

ywany jako tablica (klucz),

za pomoc

, której b

dziemy szyfrowa

i deszyfrowa

wiadomo

ci. Musi by

ona

znana przez obie komunikuj

ce si

strony (łatwo

ść

w wymianie stanowi tutaj

mikroskopijna wielko

ść

tego ła

cucha) i nie mo

e by

ujawniona nikomu innemu.

Metoda podstawieniowa

Tekst wej

ciowy stanowi

cy ci

g binarny o długo

ci n dzielony jest na ci

gi znaków

o ró

nych długo

ciach. Tablica podstawieniowa one-time-pad zbudowana jest w taki

sposób, aby wszystkie mo

liwe ci

gi wej

ciowe zostały zamienione na ci

gi znaków

zaszyfrowanych o ró

nych długo

ciach.

Szyfrowanie za pomoc

metody podstawieniowej polega na zamianie ka

dego ci

wej

ciowego na podstawie tablicy podstawieniowej na tekst wyj

ciowy

(zaszyfrowany). Deszyfrowanie jest operacj

odwrotn

Zastosowanie cz

steczek DNA w algorytmie.

Tekst wej

ciowy – probówka zawieraj

ca krótkie odcinki DNA.

Tekst zaszyfrowany – probówka zawieraj

ca inne krótkie odcinki DNA.

Szyfrowanie polega na losowej, lecz odwracalnej zamianie odcinków
reprezentuj

cych tekst wej

ciowy na odcinki DNA reprezentuj

ce tekst

zaszyfrowany. Oryginalne cz

steczki s

usuwane.

Budowa tablicy podstawieniowej:

Tworzymy długi ła

cuch DNA składaj

cy si

z wielu segmentów. Ka

dy segment

składa si

z dwóch cz

ęś

ci: ci

gu znaków reprezentuj

cych tekst jawny oraz ci

znaków reprezentuj

cych odpowiadaj

cy mu tekst zaszyfrowany.

Reprezentacja ła

cucha:

Długo

ść

ła

cucha: n.

dy segment to odcinek ograniczony z obu stron stoperem. Ła

cuch składa si

d = n / (L1+L2+L3) powtarzaj

cych si

segmentów.

– ci

g o długo

ci L1=c

log n, reprezentuj

cy tekst zaszyfrowany.

– ci

g o długo

ci L2=c

log n, reprezentuj

cy tekst jawny.

dy segment unikalnie odwzorowuje ci

g tekstu jawnego na ci

g zaszyfrowany.

STOP – primer - ci

g nukleotydów o długo

ci L3=c

Chc

c wygenerowa

sekwencj

nukleotydów, odpowiadaj

cych tekstowi

zaszyfrowanemu na podstawie tej tablicy, jako primera u

ywamy ~B

. Na jego

podstawie okre

lamy ci

g odpowiadaj

cy tekstowi jawnemu C

(reakcja PCR).

Stoper zapobiega dalszemu rozszerzaniu si

reakcji ponad interesuj

cy nas ci

jawny.

3.2 Steganografia DNA

Ludzie ju

od czasów staro

ytnych posiadali tajemnice, które chcieli ukry

przed

innymi. W wielu przypadkach uciekali si

do metod, które powodowały,

e tekst był

niewidoczny dla innych. Przykładem mo

e by

tutaj atrament sympatyczny, u

ywany

przez szpiegów czy te

miniaturowe zdj

cia wklejane do dokumentów jako kropki

ce zdania. Taki sposób ukrywania tekstu nazywamy steganografi

Prezentowany algorytm wykorzystuje w tym przypadku cz

steczki DNA.

Metoda I

Ukrywanie informacji

1. Tworzymy alfabet reprezentuj

cy znaki za pomoc

gów nukleotydów o

długo

ci 4.

2. Tekst jawny kodujemy przy pomocy stworzonego alfabetu.

3. Tworzymy klucz, który musi pozosta

tajny.

Klucz kodujemy według tego samego alfabetu, którego u

yli

my do

kodowania tekstu jawnego. Klucz stanowi starter (primer), który umo

liwia

znalezienie tekstu w

ród innych cz

steczek DNA poprzez zastosowanie

reakcji PCR. Wa

ne jest, aby po zamianie na ci

g nukleotydów, miał on

długo

ść

minimum 20 nukleotydów, aby z du

ym prawdopodobie

stwem

ród innych cz

steczek nie było wi

cej takich ci

gów. Kryptoanalityk musi

sprawdzi

) mo

liwych primerów, aby odnale

źć

wiadomo

ść

. Nie jest to

tak du

o, wi

c najlepiej aby ci

g reprezentuj

cy klucz składał si

z ponad

35 nukleotydów. Przyjmuj

c 4 nukleotydy na jeden znak, klucz powinien mie

około 9 znaków.

Budujemy ni

klucz_komplementarny-tekst-klucz_komplementarny oraz drug

, któr

stanowi klucz.

Przykładowe metody tworzenia pojedynczych nici DNA:

•

synteza na podło

u stałym,

•

metoda fotolitograficzna.

5. Wykonujemy reakcj

PCR, na skutek czego otrzymujemy dwuniciow

steczk

DNA.

6. Stworzon

steczk

umieszczamy w

ród wielu innych cz

steczek o

podobnej budowie.

Druga strona musi zna

alfabet, którego u

yto do kodowania oraz klucz (primer).

Trudno

ść

odnalezienia tekstu polega na przejrzeniu ogromnej ilo

ci cz

steczek

DNA. Odnalezienie wła

ciwej cz

steczki w tym przypadku jest równoznaczne ze

złamaniem tej metody i odnalezieniem szukanego tekstu jawnego.

Odczytywanie ukrytej informacji

1. Chc

c znale

źć

wła

ciw

steczk

DNA nale

y wykona

reakcj

PCR,

ywaj

c ła

cucha nukleotydów reprezentuj

cego klucz jako primera.

Reakcj

PCR nale

y przeprowadzi

wielokrotnie, w celu zwielokrotnienia

liczby cz

steczek zawieraj

cych ukryty tekst.

2. Po otrzymaniu pojedynczej nici z cz

steczki zawieraj

cej ukryty tekst,

odczytujemy ci

g nukleotydów (sekwencjonowanie).

3. Zamieniamy ci

g nukleotydów na poszukiwany tekst przy pomocy alfabetu,

na podstawie którego kodowali

my tekst jawny w fazie ukrywania informacji.

Najlepiej wyja

metod

na przykładzie.

Chcemy ukry

tekst jawny IT. Po zamianie tekstu na ci

g nukleotydów, otrzymujemy

nast

puj

cy ci

g: TATAGTCC.

Tworzymy hasło H2 (ze wzgl

du na czytelno

ść

przykładu hasło składa si

tylko z

dwóch znaków, natomiast w praktyce powinno by

dłu

sze). Po zamianie na ci

nukleotydów ma ono posta

: TTACACCA.

Nast

pnie tworzymy nast

puj

ce nici:

•

AATGTGGT TATAGTCC AATGTGGT,

•

TTACACCA.

Z wykorzystaniem enzymu polimerazy tworzymy podwójn

helis

DNA. Cz

steczk

umieszczamy w probówce z okre

lon

substancj

Odbiorca musi równie

dokona

zamiany hasła na ci

g nukleotydów. Nast

pnie po

otrzymaniu probówki wielokrotnie wykonuje reakcj

PCR, jako primer stosuj

c ci

nukleotydów reprezentuj

cych hasło.

Rysunek 1. Działanie reakcji PCR.

W wyniku reakcji PCR liczba cz

steczek DNA zawieraj

cych ukryty tekst zostaje

zwielokrotniona. W kolejnym kroku odbiorca wykonuje sekwencjonowanie i
otrzymuje ci

g TATAGTCC. Znaj

c alfabet zamienia go na tekst IT. Bezpiecze

stwo

tej metody oparte jest na tajno

ci klucza.

Najtrudniejsz

i najdro

reakcj

z punktu widzenia biologii jest tworzenie długich

nici o okre

lonej sekwencji nukleotydów.

Metoda II

Inne podej

cie podobne jest do kryptografii wizualnej. Tekstu nie zamieniamy teraz

według specjalnego alfabetu, lecz pewne odcinki DNA lub pojedyncze nukleotydy s

w tym przypadku odpowiednikami zer i jedynek. Równie

w tym przypadku

steczk

, któr

chcemy ukry

umieszczamy w

ród wielu innych cz

steczek.

Wszystkie cz

steczki maj

jednak podobn

budow

. Na pocz

tku i ko

cu znajduje

primer – ten sam dla wszystkich cz

steczek. W poprzedniej metodzie primer

ywany był jako klucz potrzebny do deszyfrowania wiadomo

ci. W tym przypadku

nie odgrywa on takiej roli. Jest on potrzebny, aby umo

liwi

wykonanie w

pó

niejszym etapie reakcji PCR. To wła

nie pola pomi

dzy primerami w fikcyjnych

ła

cuchach s

ywane zarówno do szyfrowania jak i deszyfrowania wła

ciwego

tekstu. Wykonuj

c elektroferez

elu otrzymujemy dla ka

dej cz

steczki oddzielne

obrazy dla 0 i 1.

Ukrywanie wiadomo

Nadawca tworzy cz

steczk

DNA z tekstem jawnym oraz primerem na jego

pocz

tku i ko

cu. Nast

pnie preparuje inne cz

steczki, które maj

podobn

budow

(długo

ść

, primery). Na podstawie obrazu

elowego tych cz

steczek (a) budowana

jest cz

steczka X (b) stanowi

ca zaszyfrowany tekst. Cz

steczka X powstaje przez

zmieszanie cz

steczek A,B,C. Nast

pnie nadawca tworzy cz

steczk

Y (b), która

powstaje przez zmieszanie cz

steczek B i C. Stanowi ona klucz potrzebny do

odczytania zaszyfrowanego tekstu. Nadawca musi przekaza

odbiorcy t

steczk

lub jej obraz

elowy.

Odkrywanie wiadomo

Za pomoc

elektroforezy

elu otrzymujemy obraz

elowy cz

steczek X oraz Y.

Nast

pnie odejmujemy od siebie obrazy X i Y, aby otrzyma

wiadomo

ść

–

steczk

A (c).

Ta metoda mo

e by

równie

czona z innymi metodami jak np. wcze

niej

omówion

metod

steganografii. Cz

steczki ze wspólnym primerem, potrzebne do

odszyfrowania wiadomo

ci mog

umieszczane w

ród wielu innych cz

steczek o

innej budowie. Primer musi stanowi

wtedy tajemnic

Przykładowe obrazy

elowe (odczytujemy od dołu do góry):

M - molekularny znacznik wagowy.

Na obrazie

elowym a) mamy przedstawione 3 cz

steczki reprezentuj

ce 9-bitowe

liczby.

1 i 2 = 100000110

= 26210 - ten ci

g chcemy ukry

3 i 4 = 001100001

= 9710

6 i 7 = 101001001

= 32910

Obraz

elowy b przedstawia cz

steczki X (zmieszane A,B i C) i Y (cz

steczki B i C).

Obraz c) prezentuje cz

steczk

A, któr

otrzymali

my przez odj

cie Y od X.

Stworzony został równie

, jak na razie czysto teoretyczny model algorytmu

szyfrowania asymetrycznego z wykorzystaniem DNA.

3.3 Skrót z u

yciem DNA

Wszystkie numery seryjne sprz

tu, płyt muzycznych, płyt z oprogramowaniem

na by kodowa

w postaci cz

steczek DNA a nast

pnie doł

cza

do przedmiotu,

którego numer ten dotyczy. Wtedy numer seryjny stałby si

ęś

fizyczn

sprz

i płyt. Takie oznaczenia zastosowano na szerok

skal

na olimpiadzie w Sydney.

Wszystkie towary zwi

zane z olimpiad

: koszulki, czapeczki a nawet kubki do kawy

zostały oznaczone specjalnym atramentem, zawieraj

cym DNA australijskiego

sportowca. Do sprawdzenia autentyczno

ci przedmiotów słu

ył skaner r

czny. W ten

sposób oznaczono ponad 50 milionów przedmiotów. Koszt oznaczenia jednego
przedmiotu wyniósł 5 centów.

3.4 Identyfikacja z u

yciem DNA

steczki DNA wykorzystywane s

do identyfikacji ludzi, szczególnie w

kryminalistyce. Fakt,

e ka

dy człowiek ma unikalny kod DNA odkrył w 1985 roku

Alec Jeffreys. Ju

rok pó

niej test DNA pozwolił skaza

pierwszych przest

pców. W

Polsce identyfikacj

genetyczn

ladów zastosowano na pocz

tku lat 90. m.in. w

sprawie zabójstwa taksówkarza w Katowicach w 1994 roku. W przypadku bada

zwi

zanych z popełnieniem przest

pstwa wykorzystuje si

introny, czyli tzw.

niekoduj

ce fragmenty ła

cucha DNA. Nie zawieraj

one informacji o cechach

człowieka a jednocze

nie umo

liwiaj

porównanie dwóch fragmentów DNA i

stwierdzenie z du

ym prawdopodobie

stwem czy pochodz

od tej samej osoby.

Wystarczy porówna

próbk

pobran

z miejsca przest

pstwa z t

uzyskan

oskar

onego. Przykładowa metoda to analiza VNTR (Variable Number of Tandem

Repeats) polegaj

ca na wyszukaniu w ła

cuchu DNA szeregu identycznych

sekwencji (np.CACACA) i zliczaniu ich długo

ci (ilo

ci powtórze

par). Liczba takich

powtórze

jest ró

na i charakterystyczna dla danej osoby. Inne zastosowanie tych

metod to testy w sprawach o ustalenie ojcostwa oraz badania medyczne (schorzenia
genetyczne). Podobne metody mogłyby by

równie

wykorzystywane jako

biometryczne metody uwierzytelniania u

ytkowników w systemach. Istnieje taka

liwo

ść

, lecz w porównaniu z identyfikacj

na podstawie obrazu t

czówki wydaje

dro

sza, trudniejsza w implementacji i zarz

dzaniu oraz wykazuje wi

ksze

prawdopodobie

stwo bł

du identyfikacji.

3.5 Kryptoanaliza algorytmów z wykorzystaniem cz

steczek DNA

Interesuj

ca jest równie

liwo

ść

wykorzystania komputerów molekularnych w

kryptoanalizie, dzi

ki ich wysokiemu stopniu zrównoleglenia. Leonard M. Adleman

pokazał,

e komputer DNA o wielko

ci kilku probówek umo

liwia odnalezienie klucza

o długo

ci 2

(metoda przeszukiwania wyczerpuj

cego, atak brutalny) algorytmu

DES. Rozwi

zanie to nie jest jednak pozbawione wad. Problem w tym przypadku

stanowi implementacja algorytmu w biochemii oraz dokładno

ść

wykonywania

oblicze

z wykorzystaniem cz

steczek DNA. Nale

y równie

pami

komputery molekularne mog

jedynie przyspieszy

rozwi

zywanie problemów,

poprzez wysoki stopie

równoległo

ci. Dla dłu

szych kluczy równie

komputery

molekularne nie umo

liwiaj

odnalezienia klucza. Przykładowo Beaver zgodnie z

podej

ciem Adlemana (atak brutalny) oszacował,

e komputer potrzebny do

faktoryzacji 1000-bitowej liczby miałby pojemno

ść

200000

litrów.

Literatura

[1]

Stryer Lubert, Biochemia. PWN, Warszawa 1999

[2]

Stepkiewicz O., Flohr M., Spirala bitów i bajtów CHIP, Grudzie

2000

[3]

Adleman Leonard, Computing with DNA, 1998,

http://www.usc.edu/dept/molecular-science/fp-sciam98.pdf

[4]

Adleman Leonard, Molecular Computations Of Solutions To Combinatorial
Problems.,

http://www.usc.edu/dept/molecular-science/fp-sci94.pdf

[5]

Adleman Leonard, Rothemund Paul W. K., Roweis Sam , Winfree Erik, On
Applying Molecular Computation To The Data Encryption Standard., 1999,

http://www.usc.edu/dept/molecular-science/fp-des96.pdf

[6]

Unold Olgierd, Wrocławski komputer molekularny,

http://pryzmat.pwr.wroc.pl/Pryzmat_170/170dna.html

[7]

Richter Ch., Leier A., Banzhaf W., Rauhe H., Private and Public Key DNA
steganography,

http://ls11

- www.cs.uni

- dortmund.de/people/banzhaf/PubKey.pdf

[8]

Gaurav Gupta, Nipun Mehra & Shumpa Chakraverty, DNA Computing, 2001,

http://www.theindianprogrammer.com/technology/dna_computing.htm

Wyszukiwarka

Podobne podstrony:
Kryptografia molekularna
w4 orbitale molekularne hybrydyzacja
kryptologia w bankowości (power point)
Biologia molekularna
W03b Komórkowe i molekularne podłoże zapaleń
Wprowadzenie do Kryptografii
kryptografia
Biologia molekularna koniugacja
genetyka molekularna
elementy genetyki molekularnej biologia 2
Przenikanie firewalli w tunelach kryptograficznych
Met. izol. oczysz.DNA dla studentów, Biologia molekularna
molekuły, egzamin - stare pytania
gielda-3, B.molekularna
seminaria biol mol onkogeneza, Płyta farmacja Poznań, III rok, Biologia molekularna, 2009, sem 6

więcej podobnych podstron