1. Zuhause
  2. Frage und Antwort
  3. Gibt es einen Algorithmus, um eine Nachricht sicher in x Teile zu teilen, die mindestens y Teile benötigen, um sie wieder zusammenzusetzen?

Gibt es einen Algorithmus, um eine Nachricht sicher in x Teile zu teilen, die mindestens y Teile benötigen, um sie wieder zusammenzusetzen?

2010-03-07 1 views
15

Gibt es einen Algorithmus, um eine Nachricht sicher in x Teile zu teilen, die mindestens y Teile benötigen, um sie wieder zusammenzusetzen? Offensichtlich, y < = x.Gibt es einen Algorithmus, um eine Nachricht sicher in x Teile zu teilen, die mindestens y Teile benötigen, um sie wieder zusammenzusetzen?

Ein Beispiel:

sagen, dass ich eine geheime Botschaft, die ich will nur im Falle meines Todes zu lesen ist. Um dies sicherzustellen, gebe ich zehn Freunden einen Bruchteil der Nachricht. Jetzt kann ich nicht garantieren, dass alle meine Freunde ihre Nachrichten zusammenfügen können, um das Original wiederherzustellen. Also konstruiere ich jeden Nachrichtenbruch so, dass nur 5 Freunde benötigt werden, um ihre Teile zusammenzusetzen, um das Ganze zu rekonstruieren. Wenn Sie jedoch weniger als 5 Teile besitzen, wird nichts über die Nachricht ausgegeben, außer möglicherweise die Länge.

Meine Frage ist, ist das möglich? Mit welchen Algorithmen könnte ich das erreichen?

Klärung bearbeiten: Der wichtige Teil davon ist die kryptografische Stärke. Ein Angreifer kann die Nachricht weder vollständig noch teilweise mit weniger als y Teilen wiederherstellen.

Quelle

2010-03-07 Aaron

+1

Ich kenne keinen solchen Algorithmus, aber ich würde definitiv daran interessiert sein, über einen zu lernen. Ich werde diesen Beitrag im Auge behalten! – Cam

Antwort

18

Shamir Secret Sharing und Blakley's scheme sind zwei gut etablierte, beweisbar sichere Mittel ein Geheimnis zu teilen, so dass es auf gestellt werden kann wenn eine vorher festgelegte Anzahl von "Aktien" kombiniert wird.

Quelle

2010-03-07 05:11:53 erickson

+0

Sind das praktische Algorithmen? –

+2

Ja, sie werden ziemlich genau für die Art von Anwendung verwendet, die das Poster beschreibt. Es gibt einige Open-Source-Implementierungen (in C, soweit ich sie gefunden habe) und sogar eine Online-Demonstration unter http://point-at-infinity.org/ssss/demo.html – erickson

+0

+1. BTW, das ist eine ausgezeichnete Demo. –

0

Klingt wie RAID 5, die x Scheiben ist erforderlich y < x eine Partition wieder zusammenzusetzen. Die Reed-Solomon error correction algorithm ist eine Implementierung dieser Art von Fehlertoleranz.

Quelle

2010-03-07 04:00:52

+0

Wissen Sie, ob dies kryptographisch stark ist? I.E. Wenn eine Person weniger als y Teile hat, wird Information über die ursprüngliche Nachricht verbreitet, oder ist es sonst plausibel, die ursprüngliche Nachricht entweder vollständig oder teilweise wiederherzustellen? – Aaron

+0

Weißt du ... das kam mir in den Sinn, als ich die Frage gelesen habe ... aber ich glaube wirklich nicht, dass das etwas mit Kryptographie zu tun hat ... Ich kenne die Details nicht, also kann ich nicht wirklich sagen ... aber AFAIK, das hat mit Redundanz und Schutz vor Datenverlust zu tun ... also ist es kein Ziel, die Daten geheim zu halten ... – Tom

+0

Oh. Ja, ich weiß nicht, dass es kryptographisch so stark ist, aber vielleicht könntest du 1) die Nutzlast mit einem großen Schlüssel verschlüsseln 2) die Nutzlast und den Schlüssel getrennt in * x * teilen 3) jedem einen Teil von jedem geben. Wenn der Schlüssel groß genug ist, dass ein Bruchteil davon ausreicht, um dich kryptografisch zu beruhigen, dann denke ich, dass es gut ist, zu gehen. Nimm einen Krypto-Nerd, um es sicher zu wissen. –

0

Ja, das ist möglich. Es heißt Vorwärtsfehlerkorrektur. Siehe http://en.wikipedia.org/wiki/Forward_error_correction

Quelle

2010-03-07 04:02:12

+0

Können Sie etwas genauer sein. Prinzipiell ist die Wiederverwendung von Fehlerkorrekturalgorithmen eine gute Idee, aber die Schwierigkeit kann darin bestehen, den richtigen Algorithmus zu wählen, dh einen mächtigen Rauschkanal (P (error) = 50%) zu tolerieren, der jedoch _nicht weniger_ als garantiert 5 Teile müssen _notwendig_ sein, um die ursprüngliche Nachricht wiederherzustellen (und natürlich, dass diese 5 Teile auch ausreichen). AFAIK (was nicht viel ist ;-)), liegt der Schwerpunkt in der Telko- und Informationstheorie auf dem _sufficient_ nicht so sehr dem _notwendigen_. – mjv

3

Überprüfen Sie http://parchive.sourceforge.net/. Es gibt eine Spezifikation und Software basiert in Reed-Solomon Code, um ein Archiv in x Teile zu teilen und y Paritätsdateien zu erstellen.

Zum Beispiel. Sie teilen ein 5mb Archiv in fünf 1mb "Daten" Dateien auf und erstellen weitere fünf 1mb "Paritäts" Dateien. Sie können Ihre ursprüngliche Datei mit einer beliebigen Kombination aus Daten- und Paritätsdateien wiederherstellen, z. B. 1 Datendatei und 4 Paritätsdateien oder 5 Paritätsdateien.

Vielleicht können Sie dies anwenden.

EDIT: Die Anwendung wäre, Ihr Archiv in X-Teile zu teilen und (X-Y) Paritätsdateien zu erstellen, dann geben Sie einen Teil und alle Paritätsdateien an jeden Empfänger. Dann könnte jedes Y von ihnen ihre Teile zusammenfügen, plus die Paritätsdateien, die sie alle teilen, um die gewünschte Ausgabe zu erzeugen.

Quelle

2010-03-07 04:56:15

2

Ich fühle, dass, anstatt Nachricht in x Teile zu teilen, Sie tatsächlich die Nachricht verschlüsseln und den Schlüssel unter y Leuten teilen können.

Ähnliches Problem in der realen Welt wird das Voting sein. Die El-Gamal-Verschlüsselung wird bei der erneuten Randomisierung verwendet, um dieses Problem zu lösen.

- Bala

Quelle

2010-03-07 06:01:48 Boolean

Verwandte Themen

 Verwandte Themen