一意のキーの生成

https://stackoverflow.com/questions/55218

09-06-2019
|

質問

特に PHP で、常に一意のキーを確実に取得できる方法を探しています。

私は次のことを行いました:

strtolower(substr(crypt(time()), 0, 7));

しかし、時々、重複キーを使用してしまうことがあります (めったにありませんが、十分な頻度で)。

私も次のことをしようと考えました:

strtolower(substr(crypt(uniqid(rand(), true)), 0, 7));

しかし、PHP Web サイトによると、uniqid() が同じマイクロ秒内に 2 回呼び出された場合、同じキーを生成する可能性があります。rand() を追加することはめったにありませんが、それでも可能だと考えています。

ユーザーの混乱を軽減するために、上記の行の後に L や O などの文字も削除しています。これが重複の原因の一部である可能性がありますが、それでも必要です。

私が考えている選択肢の 1 つは、キーを生成する Web サイトを作成し、キーをデータベースに保存して、完全に一意であることを保証することです。

他に何か考えはありますか？何らかの API を備えている、またはキーを返すだけでこれをすでに行っている Web サイトはありますか。見つけました http://userident.com ただし、キーが完全に一意になるかどうかはわかりません。

これは、ユーザー入力なしでバックグラウンドで実行する必要があります。

解決

一意の値を生成する方法は 3 つだけあり、パスワードやユーザー ID などになります。

効果的な GUID ジェネレーターを使用します。これらは長いため、縮小できません。一部のみ使用する場合 あなたは失敗します.
数値の少なくとも一部は、単一のシーケンスから連続的に生成されます。綿毛やエンコーディングを追加して、連続性をなくすことができます。利点は開始時間が短いことですが、欠点は単一のソースが必要なことです。単一ソースの制限を回避するには、ソースに番号を付けることで、[source #] + [seq #] を含めると、各ソースが独自のシーケンスを生成できるようになります。
他の手段でそれらを生成し、以前に生成された値の単一の履歴と照らし合わせてチェックします。

それ以外の方法は保証されません。基本的には 2 進数を生成しますが (コンピューターです)、それを 16 進数、10 進数、Base64、または単語リストでエンコードできることに注意してください。用途に合ったエンコーディングを選択してください。通常、ユーザーが入力したデータの場合は、Base32 の何らかのバリエーションが必要になります (これはあなたが示唆したものです)。

GUIDS に関する注意事項:それらは、その長さと生成に使用される方法から独自性の強さを獲得します。 128 ビット未満のものは安全ではありません。 乱数の生成以外にも、GUID をより一意にするために GUID に組み込まれる特性があります。これらは実質的に一意であるだけであり、完全に一意ではないことに注意してください。複製を作成することは可能ですが、実際には不可能です。

GUIDS に関するメモを更新:これを書いて以来、多くの GUID ジェネレーターが暗号的に安全な乱数ジェネレーター (次に生成される数値を予測するのが困難または不可能であり、繰り返される可能性が低い) を使用していることを知りました。実は5種類もあるんです UUIDアルゴリズム. 。アルゴリズム 4 は、Microsoft が現在 Windows GUID 生成 API に使用しているものです。あ GUID Microsoft による UUID 標準の実装です。

アップデート:7 ～ 16 文字が必要な場合は、方法 2 または 3 を使用する必要があります。

結論:率直に言って、完全にユニークなものなど存在しません。シーケンシャルジェネレーターを使用したとしても、最終的には宇宙のすべての原子を使用してストレージが不足し、自分自身にループバックして繰り返します。唯一の希望は、その地点に到達する前に宇宙が熱死することだ。

最高の乱数発生器であっても、生成している乱数の合計サイズと同じだけ繰り返す可能性があります。四半期を例に考えてみましょう。これは完全にランダムなビットジェネレーターであり、繰り返される確率は 2 分の 1 です。

したがって、すべてはあなたの独自性の基準に帰着します。シーケンスを使用してそれを Base32 エンコードすることにより、1,099,511,627,776 の数値の 8 桁で 100% の一意性を実現できます。過去の数値のリストとの照合を含まない他の方法では、一意でない確率は n/1,099,511,627,776 (n = 以前に生成された数値の数) に等しいだけです。

他のヒント

どのアルゴリズムでも重複が発生します.

したがって、既存のアルゴリズム* を使用し、単純に重複をチェックすることをお勧めできますか?

*少し追加:もし uniqid() 時間に基づいて一意でなくてもよく、呼び出しのたびに増加するグローバルカウンターも含めることができます。そうすれば、同じマイクロ秒でも何かが異なります。

コードを書かなければ、私のロジックは次のようになります。

受け入れ可能な任意の文字からランダムな文字列を生成します。
次に、日付スタンプの半分（秒の一部とすべて）を先頭に追加し、残りの半分を最後（または必要に応じて中央のどこか）に追加します。

陽気でいてください！
H

オリジナルの方法を使用する場合、パスワードの前にユーザー名または電子メールアドレスを追加すると、各ユーザーがパスワードを 1 つだけ持つことができ、常に一意になります。

同じ問題を扱った次の記事に興味があるかもしれません。 GUID はグローバルに一意ですが、GUID の部分文字列は一意ではありません.

このアルゴリズムの目標は、時間と場所の組み合わせ (相対性理論マニアにとっては「時空座標」) を一意性キーとして使用することです。ただし、時間管理は完全ではないため、たとえば、タイムスタンプが同じになるほど時間的に近い 2 つの GUID が同じマシンから連続して生成される可能性があります。そこで登場するのが一意化子です。

私は通常次のようにします:

$this->password = '';

for($i=0; $i<10; $i++)
{
    if($i%2 == 0)
        $this->password .= chr(rand(65,90));
    if($i%3 == 0)
        $this->password .= chr(rand(97,122));
    if($i%4 == 0)
        $this->password .= chr(rand(48,57));
}

理論的にはいくつかの穴があると思いますが、重複に関して問題が発生したことはありません。私は通常、一時的なパスワード（パスワードのリセット後など）にこれを使用しますが、その用途には十分に機能します。

Frank Kreuger がコメントしたように、GUID ジェネレーターを使用してください。

のようにこれです

なぜパスワードが一意である必要があるのかがまだわかりません。2 人のユーザーが同じパスワードを持っている場合の欠点は何ですか?

これは、単なる一意の識別子ではなく、ユーザー ID に関連付けられたパスワードについて話していることを前提としています。もし それは 探しているものは GUID を使用しないのはなぜでしょうか?

あなたは、Steve Gibson によるパスワード生成の非常に安全な実装に興味があるかもしれません (出典はありませんが、彼はその仕組みについて詳しく説明しています)。 https://www.grc.com/passwords.htm.

このサイトは 64 文字の巨大なパスワードを作成しますが、それらは完全にランダムであるため、最初の 8 文字 (または任意の数) を使用して、安全性は低いが「できるだけランダムな」パスワードを簡単に作成できます。

編集：後の回答から、パスワードよりも GUID のようなものが必要であることがわかりました。したがって、これはおそらくあなたが望むものではありません...

あなたの問題の一部は、単一の関数を 2 つの異なる用途に使用しようとしているということだと思います...パスワードとtransaction_id

これらは実際には 2 つの異なる問題領域であり、一緒に対処しようとすることは実際には最善ではありません。

最近、手早く簡単なランダムな一意のキーが必要だったので、次のことを行いました。

$ukey = dechex(time()) . crypt( time() . md5(microtime() + mt_rand(0, 100000)) );

したがって、基本的には Unix 時間を秒単位で取得し、時間 + 乱数から生成されたランダムな md5 文字列を追加します。これは最高ではありませんが、低頻度のリクエストではかなり優れています。高速で動作します。

何千ものキーを生成して繰り返しを探すテストを行ったところ、1 秒あたり約 800 個のキーがあったので繰り返しはなく、悪くありませんでした。それは完全に mt_rand() に依存すると思います

私はこれをアンケートトラッカーに使用しており、1 分あたり約 1000 件のアンケートを送信できます...したがって、今のところ（残念ながら）重複はありません。もちろん、レートは一定ではありません (1 日の特定の時間に提出物を受け取ります)。そのため、これは確実ではありませんし、最善の解決策でもありません...ヒントは、キーの一部として増分値を使用することです (私の場合は time() を使用しましたが、もっと良い可能性があります)。

一意の値の作成とはあまり関係のない暗号化部分を無視して、私は通常これを使用します。

function GetUniqueValue()
{
   static $counter = 0; //initalized only 1st time function is called
   return strtr(microtime(), array('.' => '', ' ' => '')) . $counter++;
}

同じプロセス内で呼び出された場合、$counter が増加するため、値は同じプロセス内で常に一意になります。

異なるプロセスで呼び出された場合、同じ値を持つ 2 つの microtime() 呼び出しが発生するのは本当に運が悪いに違いありません。microtime() 呼び出しは、同じスクリプト内で呼び出された場合でも通常は異なる値を持つと考えてください。

私は通常、ランダムな部分文字列 (ユーザーの便宜のために 8 ～ 32 文字以下の文字数をランダム化する)、または取得した値、時間、またはそれらの組み合わせの MD5 を使用します。よりランダム性を高めるために、取得した値 (姓など) を MD5 して時刻と連結し、再度 MD5 して、ランダムな部分文字列を取得します。そう、あなた できた 同等のパスワードを取得できますが、その可能性はまったくありません。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow