Pi mit PhP

T

tx_g

Gast
Hallo,
ich benötige für eines meiner Scripte einen Algorithmus welcher mir so viele Nachkommastellen von Pi wie möglich als Zeichenkette zurückgibt. (Bzw so viele wie ich haben will z.bsp zum einstellen.)
bei meiner Suche bin ich bereits auf etwas gestoßen:
https://github.com/msipos/syntaxic/blob/master/examples/php/pidigits.php-5.php
Leider ist das für meine Zwecke, zum generieren von Passwörtern deutlich zu langsam. Man bekommt knapp 50k Stellen in 40-50 Sekunden raus. Das ist keine Wartezeit die man bei Webanwendungen haben will, wo diese Passwort sich immer selbst generieren soll.

Kennt ihr einen weg mit dem ich das ganze möglichst 20-100x schneller durch bekomme?
 
Wo ist der Zusammenhang zwischen Pi und Passwörtern?
 
Muss es Pi sein oder tut es jede irrationale Zahl? Irrationale Zahlen sind genau die mit unendlichen, nicht-periodischen Dezimalbruchentwicklungen; für die gibt es das Heronverfahren oder babylonische Wurzelziehen, das eine sehr hohe Konvergenzgeschwindigkeit hat und nur "billige" Operationen braucht.

Edit: An den über mir: Vermutlich weil in der Dezimalbruchentwicklung alle Ziffern von 1-9 in nicht-periodischer Art und Weise auftauchen.
 
Zuletzt bearbeitet:
Du willst also Passwörter generieren?! Wieso brauchst du dafür Pi? Klingt nach: http://xyproblem.info/

Edit: @Rage: Und wozu braucht man das? Pi ist genau so wenig zufällig, wie 1 oder 2. Und wenn die Nachkommastellen als Passwort genutzt werden, steht die Timing-Attacke vor der Haustür: Du kannst über die Laufdauer drauf schließen, wie weit Pi errechnet wurde und das Passwort erraten.
 
Zuletzt bearbeitet:
Nein, Pi ist nicht zufällig (was auch immer das für eine Zahl heißen soll) aber es gibt kein Muster nach dem die Ziffern in der Dezimalbruchentwicklung auftauchen. Man kann diese Ziffern also möglicherweise als Startwerte für irgendwas anderes benutzen.
 
Jedoch sollten auch Seeds möglichst zufällig sein, sonst sind die damit generierten Daten nämlich genauso wenig "zufällig".
 
Wie soll ich das gut erklären.
Ich nutze Pi um dort Teilstücke auszuschneiden und weiterzu verrechnen. Das ganze bietet sich an da alle Nachkommastellen berechenbar sind und ich immer die gleichen Schnipsel zur selben Zeit raus bekomme. Und so generieren ich in Kurzform mit etwas drum herum Passwörter.

Vermutlich tut es jede irrationale Zahl. Pi ist mir nur als erstes eingefallen.
 
Woher soll denn irgendein Angreifer die irrationale Zahl raten, von der der Seed kommt? Und dann auch noch, welche Ziffern genutzt wurden? Es gibt eine sehr viel größere Menge an irrationalen Zahlen als rationale Zahlen.
 
Nimm einfach random-bytes, ein vom User vergebenes Passwort und jage es durch pbkdf2 oder Ähnliches.


Bspw. wie Fortatus schon sagte über Timing Attacks. Selbst bei 1.000.000 Stellen von Pi die man berechnen lässt sollte das Leute dies drauf anlegen nicht großartig hindern.
 
Zuletzt bearbeitet:
Wenn du einen zufälligen String haben willst, der als Passwort genutzt wird, dann einfach http://php.net/manual/en/function.random-bytes.php aufrufen und gut ist. Wenn kein PHP7 zur Verfügung steht, gibt es eine Bibliothek, die es in PHP5 nachrüstet.

Das haben Profis geschrieben, die was von Sicherheit verstehen und da kommt besserer Zufall raus, als wenn du mit Pi rumhantierst.
 
Es geht ja darum das ich mit den selben Parametern zur selben Zeit (24h)immer das selbe Passwort raus bekomme, da jede Anwendung das Passwort selbst erzeugen soll um auf das System zu zu greifen. Und da zufällige zahlen nun doch eher unkontrolliert umherwandern ist man mit einer fixen Zahlenkette besser beraten.
 
Natürlich gibt es immer eine bessere Methode, um (Pseudo-)Zufallszahlen zu generieren, dagegen hab ich überhaupt nichts gesagt. Ich habe nur eine definitiv wirtschaftliche Möglichkeit aufgezeigt, um das, was der TE möchte, zu realisieren (denn das hängt nicht von Pi ab, sondern nur von der Eigenschaft, eine irrationale Zahl zu sein). Wenn es eine eingebaute Funktion gibt, die das besser kann, ist das ja nur gut so.
 
Sag uns doch überhaupt erstmal, wofür du das benutzen willst. Das ist ein totales XY-Problem: http://xyproblem.info/

Willst du einen Authenticator bauen, für Zwei-Faktor-Authentifzierung? Wir raten hier nur rum, was dein eigentliches Problem ist.
 
Hm. Ich gebe Mal den Code her. Das ganze ist als Beispiel gedacht, wird also in der Form letztendlich nicht mehr genutzt.
PHP:
<?php
define( 'WP_DEBUG', true );
ini_set('display_errors', 1);
error_reporting(E_ALL);

$startzeit = time();

$mainkey ="123";
setdate($mainkey, $startzeit);

function setdate($mainkey, $startzeit){
$day = date("d"); //1-31
$month = date("m"); //1-12
$year = date("Y"); //xxxx
$dayofyear = date("z");//1-365
$dayofweek = date("N");//1-7
$dayspermonth = date("t");//28-31
$leapyear = date("L")+1;//0+1 or 1+1 //1-2
generatetimevalues($day, $month, $year, $dayofyear, $dayofweek, $dayspermonth, $leapyear, $mainkey, $startzeit);
}

function generatetimevalues($day, $month, $year, $dayofyear, $dayofweek, $dayspermonth, $leapyear, $mainkey, $startzeit){
//Buntes Würfeln :D
if($day % 2 != 0){$a=$day;} else{$a=$year;}
if($month% 2 != 0){$b=$month;} else{$b=$dayofyear;}
if($year% 2 != 0){$c=$year;} else{$c=$dayspermonth;}
if($dayofyear% 2 != 0){$d=$dayofyear;} else{$d=$leapyear;}
if($dayofweek% 2 != 0){$e=$dayofweek;} else{$e=$month;}
if($dayspermonth% 2 != 0){$f=$dayspermonth;} else{$f=$dayofweek;}
if($leapyear% 2 != 0){$g=$leapyear;} else{$g=$day;}
//Einsetzen in simple Rechenaufgaben
$ta = abs($a*$b);
$tb = abs($a-$e);
$tc = abs($g+$f);
$td = abs($d/($a+$f));
$te = abs($c*24);
$tf = abs($g*$f*$a);
$tg = abs($d-$e/(27-$f));
$th = abs(($a+$b+$c)/($d-$e-$f));
$tstr = round(abs(((($tg-$tf)*($td+$ta))+(2*$te))/($tc-$tb)));
generatepistr($ta, $tb, $tc, $td, $te, $tf, $tg, $th, $tstr, $mainkey, $startzeit);
}

function generatepistr($ta, $tb, $tc, $td, $te, $tf, $tg, $th, $tstr, $mainkey, $startzeit){
//Festlegen der Berechnungsgrenze von Pi
$timevalues = array($ta, $tb, $tc, $td, $te, $tf, $tg, $th);
$maxtimevalue = max($timevalues);
$pilength = $maxtimevalue+5;
//Berechnen von Pi
ob_implicit_flush(1);
ob_start(NULL, 4096);
$w = gmp_init(0);
$k = 1;
$n1 = gmp_init(4);
$n2 = gmp_init(3);
$d = gmp_init(1);
$i = 0;
$pi = null;
while(true) {
   $u = gmp_div_q($n1, $d);
   $v = gmp_div_q($n2, $d);
   if(gmp_cmp($u, $v) == 0) {
      $pi = $pi."".gmp_strval($u)."";
      ++$i;
      if($i % 10 == 0) {
      }
      if($i == $pilength) {
         break;
      }
      $u = gmp_mul($d, gmp_mul(-10, $u));
      $n1 = gmp_mul($n1, 10);
      $n1 = gmp_add($n1, $u);
      $n2 = gmp_mul($n2, 10);
      $n2 = gmp_add($n2, $u);
   } else {
      $k2 = $k << 1;
      $u = gmp_mul($n1, $k2 - 1);
      $v = gmp_add($n2, $n2);
      $w = gmp_mul($n1, $k - 1);
      $n1 = gmp_add($u, $v);
      $u = gmp_mul($n2, $k + 2);
      $n2 = gmp_add($w, $u);
      $d = gmp_mul($d, $k2 + 1);
      ++$k;
   }
}
$pistopzeit = time();
//Ausgabe von Pi in $pi
//Finden einzelner Abschnitte in pi
$pia = substr($pi, $ta, 5);
$pib = substr($pi, $tb, 5);
$pic = substr($pi, $tc, 5);
$pid = substr($pi, $td, 5);
$pie = substr($pi, $te, 5);
$pistr = round(abs(((($pia*$pic)/($pie-$pid))*$pib+$pic)*((round(pi())*$pie))));
generatehash($mainkey, $tstr, $pistr, $startzeit, $pilength);
}

function generatehash($mainkey, $tstr, $pistr, $startzeit, $pilength){
//Md5 oder SHA1
if ($tstr % 2 != 0){$tstrhash = md5($tstr);} else {$tstrhash = sha1($tstr);}
if ($pistr % 2 != 0){$pistrhash = sha1($pistr);} else {$pistrhash = md5($pistr);}
//Zaubern mit hash_hmac("sha256", $value, $key);
$keyla = hash_hmac("sha256", $pistrhash, $tstrhash);
$keylb = hash_hmac("sha256", $tstrhash, $pistrhash);
$keylc = hash_hmac("sha256", $tstr, $pistr);
$keyld = hash_hmac("sha256", $pistr, $tstr);
//Zusammenführen
$keylx = "$keylc$keyla";
$keyly = "$keylb$keyld";
$keyz = hash_hmac("sha256", $keylx, $keyly);
$key = hash_hmac("sha256", $keyz, $mainkey);
ausgabe($key, $startzeit, $pilength);
}

function ausgabe($key, $startzeit, $pilength){
$stopzeit = time();
$laufzeit = $stopzeit-$startzeit;
echo "<p>";
echo "Rechendauer: ".$laufzeit." s";
echo "</p>";
echo "<p>";
echo "Stellen von Pi:".$pilength;
echo "</p>";

$da = date("d");
$mo = date("m");
$ye = date("y");
$aktuell = " ".$da."-".$mo."-".$ye;
$da2 = $da+1;
$bis = " ".$da2."-".$mo."-".$ye;
echo "<p>";
echo "Dieser Key ist von $aktuell bis $bis gültig.";
echo "</p>";
echo "<p>";
echo $key;
echo "</p>";
}
?>
Das Problem dabei ist, das der Teil der Pi generiert so langsam ist das das ganze System nicht so wirklich zu gebrauchen ist.
(Abgesehen das teilweise Aktionen noch keinen so wirklichen Sinn machen, aber da bin ich noch nicht :) )

Gut hier und da sind noch ein paar komische Dinger im Code, von vorhergehenden Tests, habe ich vergessen rauszunehmen.
In Aktion sieht man den hier, wenn ich das so zeigen darf:
https://horstexplorer.lima-city.de/Key/
Ergebnis 13.11.:
e21ccc3f540d44edc0298077c63b2a0185415a24b4569bbdc770333c4967996f
Ergebnis 14.11.:
 
Zuletzt bearbeitet von einem Moderator:
Willst du uns nicht lieber sagen was du vorhast?

Selbst wenn du Pi auf 1.000.000 Stellen berechnest, dann gibt es immer noch nur etwa 500 Milliarden Möglichkeiten daraus Zahlenketten zu extrahieren. In Kombi mit ner Timing Attack ist das wohl ziemlich schnell geknackt.

Zum Vergleich: Ein Passwort mit 12 Stellen a-z, A-Z, 0-9 hat laut Wolframalpha "3 sextillion 226 quintillion 266 quadrillion 762 trillion 397 billion 899 million 821 thousand 56" Möglichkeiten.

Und zumindest für 10 stellige Passwörte liefert der erste Treffer auf Google schon eine passende Rainbowtable.
 
Zuletzt bearbeitet:
Willst du uns nicht lieber sagen was du vorhast?
Nun ja, da wo es derzeit das Problem gibt, ist bei dem berechnen einer irrationalen Zahl. Das dauert bei Pi einfach zu lang.

Im ganzen geht es darum, ein beliebiges System aus Datenbank und Anwendungsscripten so abzusichern, das jedes Script auf die Datenbank problemlos zugreifen können soll, aber niemand so wirklich (also ohne sich da eines der Anwendungen außeinander zu nehmen) selbst in der Datenbank rum fummeln kann. Natürlich könnte man da einfach ein ewig langes Passwort zufällig eingeben welches man sich sicherlich nicht merkt, aber wenn sich das Passwort von selbst alle 24h ändert gibt das noch nen ganz anderen Schwierigkeitsgrad das rauszufinden. Zumindest theoretisch.
 
:lol:

Sowas löst man in der Regel über einen Webservice.
 
Die Idee mit Pi ist naiv gedacht gut, beim genauen Betrachten aber Mist.

​Eine wirklich einfache Lösung, die halbwegs sicher und dabei noch schnell ist:

Code:
function generate_key($secret,$livetime){
return sha1((floor(time()/$livetime).$secret);//Hier eine aktuelle Passworthashfunktion einfügen, sha1 ist mittlerweile geknackt
​}
echo "Der Key ".generate_key('blah',10)." ist für das secret 'blah' für 10 Sekunden gültig";
​
Die Idee ist, dass die Zeit ein Teil des Schlüssels ist, der andere Teil kommt aus dem vorher ausgetauschten Passwort ($secret). Ein Problem hier ist, dass ich durch das Abfangen des Keys während des Zeitfensters Zugriff bekomme, aber wie immer gilt: "Don't write your own crypto".

​EDIT: zusätzliche Posts während des Schreibens:
Das ist überhaupt keine Sicherheit, vor allem nicht, wenn es sich nur alle 24 h ändert. So kann ich einen ganzen Tag arbeiten und muss den Schlüssel nicht ändern. Am nächsten Tag stelle ich eine Anfrage an den Server und les wie beim ersten Mal den Schlüssel aus. Also schreib ich ein Script, welches jeden Tag den Tagesschlüssel ausliest... viel zu einfach.
​Normalerweise stellt solche Sachen auf dem Server und nicht auf dem Client sicher. "Don't trust the client" "Validate every input".
 
Zuletzt bearbeitet:
So in der Art ist es ja bereits aufgebaut.
Ich nehme die Zeit, verwurste die, suche mir die Zeichenfolge von Pi ab Stelle der verwüsteten zahlen herraus, vermische das ganze wieder, hashe das ganze mit billig md5 oä, setze das in
hash_hmac in mehreren Kombinationen ein, wieder verwursten, dann noch mal drüber. Das der letzte Key mit 123 nicht ganz so gut ist ja da muss ich noch was ändern. Aber das ist so ungefähr das selbe in etwas umständlicher.

Wie meinst du eigentlich das mit dem abfangen des Keys?
Das ganze wird lokal auf dem Server generiert wo es auch benutzt wird. Da wo es jetzt liegt ist es nur als Funktionstest, weil das ganze etwas schneller zu bedienen ist.
 
Zuletzt bearbeitet von einem Moderator:
Zurück
Oben