<HTML><HEAD>
<META content="text/html; charset=ISO-8859-1" http-equiv=Content-Type></HEAD>
<BODY dir=ltr bgColor=#ffffff text=#000000>
<DIV dir=ltr>
<DIV style="FONT-FAMILY: 'Calibri'; COLOR: #000000; FONT-SIZE: 12pt">
<DIV>Nee het is volgens mij onmogelijk een encryptie algoritme te bedenken dat
onmogelijk gebroken kan worden, maar dat hangt er vooral vanaf wat je met breken
bedoelt.</DIV>
<DIV> </DIV>
<DIV>ALS je een methode hebt om te verifiëren dat je iets succesvol hebt
gedecrypt (het resultaat lijkt op plain text bijvoorbeeld), kun je altijd gewoon
alle mogelijke sleutels proberen tot je er bent (de definitie van een brute
force aanval), en gegeven genoeg pogingen lukt het dus altijd.</DIV>
<DIV>Als het benodigde aantal pogingen qua tijd in dezelfde orde als de leeftijd
van het universum begint te komen, zit je veilig, totdat een algoritme echt
gekraakt wordt. Een algoritme is “gekraakt” als je een manier kan verzinnen die
sneller is dan die brute force.</DIV>
<DIV> </DIV>
<DIV>Het probleem is met een kwantumcomputer: als je normaal 1 bitje toevoegt
aan de sleutel, moet je twee keer zo vaak proberen met een gewone computer, maar
met een kwantumcomputer hoef je maar een “paar keer” extra te proberen
(moeilijkheid is niet meer exponentieel met de lengte van de sleutel)</DIV>
<DIV> </DIV>
<DIV>Wikipedia: <A title=https://en.wikipedia.org/wiki/Shor_algorithm
href="https://en.wikipedia.org/wiki/Shor_algorithm">https://en.wikipedia.org/wiki/Shor_algorithm</A></DIV>
<P><FONT face="Times New Roman"><B>Shor's algorithm</B>, named after
mathematician </FONT><A title="Peter Shor"
href="https://en.wikipedia.org/wiki/Peter_Shor"><FONT
face="Times New Roman">Peter Shor</FONT></A><FONT face="Times New Roman">, is a
</FONT><A title="Quantum algorithm"
href="https://en.wikipedia.org/wiki/Quantum_algorithm"><FONT
face="Times New Roman">quantum algorithm</FONT></A><FONT face="Times New Roman">
(an </FONT><A title=Algorithm
href="https://en.wikipedia.org/wiki/Algorithm"><FONT
face="Times New Roman">algorithm</FONT></A><FONT face="Times New Roman"> which
runs on a </FONT><A title="Quantum computer"
href="https://en.wikipedia.org/wiki/Quantum_computer"><FONT
face="Times New Roman">quantum computer</FONT></A><FONT face="Times New Roman">)
for </FONT><A title="Integer factorization"
href="https://en.wikipedia.org/wiki/Integer_factorization"><FONT
face="Times New Roman">integer factorization</FONT></A><FONT
face="Times New Roman"> formulated in 1994. Informally it solves the following
problem: Given an integer <I>N</I>, find its </FONT><A title="Prime factor"
href="https://en.wikipedia.org/wiki/Prime_factor"><FONT
face="Times New Roman">prime factors</FONT></A><FONT
face="Times New Roman">.</FONT></P>
<P><FONT face="Times New Roman">On a quantum computer, to factor an integer
<I>N</I>, Shor's algorithm runs in </FONT><A class=mw-redirect
title="Polynomial time"
href="https://en.wikipedia.org/wiki/Polynomial_time"><FONT
face="Times New Roman">polynomial time</FONT></A><FONT face="Times New Roman">
(the time taken is polynomial in log <I>N</I>, which is the size of the
input).<SUP id=cite_ref-1 class=reference><A
href="https://en.wikipedia.org/wiki/Shor_algorithm#cite_note-1"><SPAN>[</SPAN>1<SPAN>]</SPAN></A></SUP>
Specifically it takes time <SPAN class=texhtml><A title="Big O notation"
href="https://en.wikipedia.org/wiki/Big_O_notation">O</A>((log
<I>N</I>)<SUP>3</SUP>)</SPAN>, demonstrating that the integer factorization
problem can be efficiently solved on a quantum computer and is thus in the
</FONT><A title="Complexity class"
href="https://en.wikipedia.org/wiki/Complexity_class"><FONT
face="Times New Roman">complexity class</FONT></A><FONT face="Times New Roman">
<B><A title=BQP href="https://en.wikipedia.org/wiki/BQP">BQP</A></B>. This is
exponentially faster than the most efficient known classical factoring
algorithm, the </FONT><A title="General number field sieve"
href="https://en.wikipedia.org/wiki/General_number_field_sieve"><FONT
face="Times New Roman">general number field sieve</FONT></A><FONT
face="Times New Roman">, which works in </FONT><A class=mw-redirect
title="Sub-exponential time"
href="https://en.wikipedia.org/wiki/Sub-exponential_time"><FONT
face="Times New Roman">sub-exponential time</FONT></A><FONT
face="Times New Roman"> — about <SPAN class=texhtml>O(e<SUP>1.9 (log
N)<SUP>1/3</SUP> (log log N)<SUP>2/3</SUP></SUP>)</SPAN>.<SUP id=cite_ref-2
class=reference><A
href="https://en.wikipedia.org/wiki/Shor_algorithm#cite_note-2"><SPAN>[</SPAN>2<SPAN>]</SPAN></A></SUP>
The efficiency of Shor's algorithm is due to the efficiency of the </FONT><A
title="Quantum Fourier transform"
href="https://en.wikipedia.org/wiki/Quantum_Fourier_transform"><FONT
face="Times New Roman">quantum Fourier transform</FONT></A><FONT
face="Times New Roman">, and </FONT><A title="Modular exponentiation"
href="https://en.wikipedia.org/wiki/Modular_exponentiation"><FONT
face="Times New Roman">modular exponentiation</FONT></A><FONT
face="Times New Roman"> by </FONT><A title="Exponentiation by squaring"
href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring"><FONT
face="Times New Roman">squarings</FONT></A><FONT
face="Times New Roman">.</FONT></P>
<P><FONT face="Times New Roman">If a quantum computer with a sufficient number
of </FONT><A class=mw-redirect title=Qubits
href="https://en.wikipedia.org/wiki/Qubits"><FONT
face="Times New Roman">qubits</FONT></A><FONT face="Times New Roman"> were to be
constructed, Shor's algorithm could be used to break </FONT><A
title="Public-key cryptography"
href="https://en.wikipedia.org/wiki/Public-key_cryptography"><FONT
face="Times New Roman">public-key cryptography</FONT></A><FONT
face="Times New Roman"> schemes such as the widely used </FONT><A
title="RSA (algorithm)"
href="https://en.wikipedia.org/wiki/RSA_%28algorithm%29"><FONT
face="Times New Roman">RSA</FONT></A><FONT face="Times New Roman"> scheme. RSA
is based on the assumption that factoring large numbers is computationally
infeasible. So far as is known, this assumption is valid for classical
(non-quantum) computers; no classical algorithm is known that can factor in
polynomial time. However, Shor's algorithm shows that factoring is efficient on
a quantum computer, so a sufficiently large quantum computer can break RSA. It
was also a powerful motivator for the design and construction of quantum
computers and for the study of new quantum computer algorithms. It has also
facilitated research on new cryptosystems that are secure from quantum
computers, collectively called </FONT><A title="Post-quantum cryptography"
href="https://en.wikipedia.org/wiki/Post-quantum_cryptography"><FONT
face="Times New Roman">post-quantum cryptography</FONT></A><FONT
face="Times New Roman">.</FONT></P>
<P><FONT face="Times New Roman">In 2001, Shor's algorithm was demonstrated by a
group at IBM, who factored 15 into 3 × 5, using an </FONT><A class=mw-redirect
title="Nuclear magnetic resonance (NMR) quantum computing"
href="https://en.wikipedia.org/wiki/Nuclear_magnetic_resonance_%28NMR%29_quantum_computing"><FONT
face="Times New Roman">NMR implementation</FONT></A><FONT
face="Times New Roman"> of a quantum computer with 7 </FONT><A class=mw-redirect
title=Qubits href="https://en.wikipedia.org/wiki/Qubits"><FONT
face="Times New Roman">qubits</FONT></A><FONT face="Times New Roman">.<SUP
id=cite_ref-VSBYSC01_3-0 class=reference><A
href="https://en.wikipedia.org/wiki/Shor_algorithm#cite_note-VSBYSC01-3"><SPAN>[</SPAN>3<SPAN>]</SPAN></A></SUP>
However, some doubts have been raised as to whether IBM's experiment was a true
demonstration of quantum computation, since no </FONT><A
title="Quantum entanglement"
href="https://en.wikipedia.org/wiki/Quantum_entanglement"><FONT
face="Times New Roman">entanglement</FONT></A><FONT face="Times New Roman"> was
observed.<SUP id=cite_ref-BCJLPS99_4-0 class=reference><A
href="https://en.wikipedia.org/wiki/Shor_algorithm#cite_note-BCJLPS99-4"><SPAN>[</SPAN>4<SPAN>]</SPAN></A></SUP>
Since IBM's implementation, several other groups have implemented Shor's
algorithm using photonic qubits, emphasizing that entanglement was observed.<SUP
id=cite_ref-LBYP07_5-0 class=reference><A
href="https://en.wikipedia.org/wiki/Shor_algorithm#cite_note-LBYP07-5"><SPAN>[</SPAN>5<SPAN>]</SPAN></A></SUP><SUP
id=cite_ref-LWLBJGW07_6-0 class=reference><A
href="https://en.wikipedia.org/wiki/Shor_algorithm#cite_note-LWLBJGW07-6"><SPAN>[</SPAN>6<SPAN>]</SPAN></A></SUP>
In 2012, the factorization of 15 was repeated.<SUP id=cite_ref-7
class=reference><A
href="https://en.wikipedia.org/wiki/Shor_algorithm#cite_note-7"><SPAN>[</SPAN>7<SPAN>]</SPAN></A></SUP>
Also in 2012, the factorization of 21 was achieved, setting the record for the
largest number factored with a quantum computer. <SUP id=cite_ref-8
class=reference><A
href="https://en.wikipedia.org/wiki/Shor_algorithm#cite_note-8"><SPAN>[</SPAN>8<SPAN>]</SPAN></A></SUP></FONT></P>
<DIV
style="FONT-STYLE: normal; DISPLAY: inline; FONT-FAMILY: 'Calibri'; COLOR: #000000; FONT-SIZE: small; FONT-WEIGHT: normal; TEXT-DECORATION: none">
<DIV style="FONT: 10pt tahoma">
<DIV> </DIV>
<DIV style="BACKGROUND: #f5f5f5">
<DIV style="font-color: black"><B>From:</B> <A title=antior@piratenpartij.nl
href="mailto:antior@piratenpartij.nl">Antior</A> </DIV>
<DIV><B>Sent:</B> Monday, December 03, 2012 2:11 PM</DIV>
<DIV><B>To:</B> <A title=algemeen@lists.piratenpartij.nl
href="mailto:algemeen@lists.piratenpartij.nl">algemeen@lists.piratenpartij.nl</A>
</DIV>
<DIV><B>Subject:</B> Re: [Algemeen] Verdacht DNA?</DIV></DIV></DIV>
<DIV> </DIV></DIV>
<DIV
style="FONT-STYLE: normal; DISPLAY: inline; FONT-FAMILY: 'Calibri'; COLOR: #000000; FONT-SIZE: small; FONT-WEIGHT: normal; TEXT-DECORATION: none">
<DIV class=moz-cite-prefix>Vraag: Het is mogelijk om met een gewone computer een
encryptie te schrijven die niet met diezelfde computer gekraakt kan worden. Dat
is hoe de meeste moderne encryptiemethoden immers werken.<BR><BR>Is het mogelijk
om een bestand via een quantumcomputer zodanig te encrypten dat hij niet met een
quantumcomputer gekraakt kan worden?<BR><BR>-
Antior<BR></DIV></DIV></DIV></DIV></BODY></HTML>