java random - Почему этот код использует случайные строки для печати «hello world»?




string securerandom (13)

Следующий оператор печати напечатает «hello world». Может ли кто-нибудь объяснить это?

System.out.println(randomString(-229985452) + " " + randomString(-147909649));

А randomString() выглядит так:

public static String randomString(int i)
{
    Random ran = new Random(i);
    StringBuilder sb = new StringBuilder();
    while (true)
    {
        int k = ran.nextInt(27);
        if (k == 0)
            break;

        sb.append((char)('`' + k));
    }

    return sb.toString();
}

Answers

Случайные всегда возвращают одну и ту же последовательность. Он используется для перетасовки массивов и других операций в качестве перестановок.

Чтобы получить разные последовательности, необходимо инициализировать последовательность в некотором положении, называемую «семя».

Случайное значение получает случайное число в позиции i (seed = -229985452) «случайной» последовательности. Затем использует код ASCII для следующего 27 символов в последовательности после позиции семени, пока это значение не станет равно 0. Это возвращает «привет». Та же операция выполняется для «мира».

Я думаю, что код не работал ни на какие другие слова. Парень, который запрограммировал это, хорошо знает случайную последовательность.

Это очень классный код!


Я просто оставлю это здесь. Тот, у кого есть много (CPU) времени, чтобы избавиться, не стесняйтесь экспериментировать :) Кроме того, если вы освоили некоторый fork-join-fu, чтобы заставить эту вещь записывать все ядра процессора (просто потоки скучны, правильно?), Пожалуйста, поделитесь ваш код. Буду весьма признателен за это.

public static void main(String[] args) {
    long time = System.currentTimeMillis();
    generate("stack");
    generate("over");
    generate("flow");
    generate("rulez");

    System.out.println("Took " + (System.currentTimeMillis() - time) + " ms");
}

private static void generate(String goal) {
    long[] seed = generateSeed(goal, Long.MIN_VALUE, Long.MAX_VALUE);
    System.out.println(seed[0]);
    System.out.println(randomString(seed[0], (char) seed[1]));
}

public static long[] generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();
    char[] pool = new char[input.length];
    label:
    for (long seed = start; seed < finish; seed++) {
        Random random = new Random(seed);

        for (int i = 0; i < input.length; i++)
            pool[i] = (char) random.nextInt(27);

        if (random.nextInt(27) == 0) {
            int base = input[0] - pool[0];
            for (int i = 1; i < input.length; i++) {
                if (input[i] - pool[i] != base)
                    continue label;
            }
            return new long[]{seed, base};
        }

    }

    throw new NoSuchElementException("Sorry :/");
}

public static String randomString(long i, char base) {
    System.out.println("Using base: '" + base + "'");
    Random ran = new Random(i);
    StringBuilder sb = new StringBuilder();
    for (int n = 0; ; n++) {
        int k = ran.nextInt(27);
        if (k == 0)
            break;

        sb.append((char) (base + k));
    }

    return sb.toString();
}

Выход:

-9223372036808280701
Using base: 'Z'
stack
-9223372036853943469
Using base: 'b'
over
-9223372036852834412
Using base: 'e'
flow
-9223372036838149518
Using base: 'd'
rulez
Took 7087 ms

Я был заинтригован этим, я запустил этот генератор случайных слов в списке словарных слов. Диапазон: Integer.MIN_VALUE для Integer.MAX_VALUE

Я получил 15131 хитов.

int[] arrInt = {-2146926310, -1885533740, -274140519, 
                -2145247212, -1845077092, -2143584283,
                -2147483454, -2138225126, -2147375969};

for(int seed : arrInt){
    System.out.print(randomString(seed) + " ");
}

Печать

the quick browny fox jumps over a lazy dog 

Речь идет о «семени». Те же самые семена дают одинаковый результат.


Из документов Java это преднамеренная функция при определении начального значения для класса Random.

Если два экземпляра Random создаются с одним и тем же семенем, и для каждой из них производится одна и та же последовательность вызовов методов, они будут генерировать и возвращать идентичные последовательности чисел. Чтобы гарантировать это свойство, для класса Random задаются определенные алгоритмы. Java-реализации должны использовать все алгоритмы, показанные здесь для класса Random, для абсолютной переносимости Java-кода.

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Random.html

Однако, несмотря на это, вы можете подумать, что существуют неявные проблемы безопасности при наличии предсказуемых «случайных» чисел.


Полученный из ответа Дениса Тульского , этот метод генерирует семя.

public static long generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();
    char[] pool = new char[input.length];
    label:
        for (long seed = start; seed < finish; seed++) {
            Random random = new Random(seed);

            for (int i = 0; i < input.length; i++)
                pool[i] = (char) (random.nextInt(27)+'`');

            if (random.nextInt(27) == 0) {
                for (int i = 0; i < input.length; i++) {
                    if (input[i] != pool[i])
                        continue label;
                }
                return seed;
            }

        }

    throw new NoSuchElementException("Sorry :/");
}

Поскольку многопоточность очень проста с Java, вот вариант, который ищет семя, используя все доступные ядра: http://ideone.com/ROhmTA

import java.util.ArrayList;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadFactory;

public class SeedFinder {

  static class SearchTask implements Callable<Long> {

    private final char[] goal;
    private final long start, step;

    public SearchTask(final String goal, final long offset, final long step) {
      final char[] goalAsArray = goal.toCharArray();
      this.goal = new char[goalAsArray.length + 1];
      System.arraycopy(goalAsArray, 0, this.goal, 0, goalAsArray.length);
      this.start = Long.MIN_VALUE + offset;
      this.step = step;
    }

    @Override
    public Long call() throws Exception {
      final long LIMIT = Long.MAX_VALUE - this.step;
      final Random random = new Random();
      int position, rnd;
      long seed = this.start;

      while ((Thread.interrupted() == false) && (seed < LIMIT)) {
        random.setSeed(seed);
        position = 0;
        rnd = random.nextInt(27);
        while (((rnd == 0) && (this.goal[position] == 0))
                || ((char) ('`' + rnd) == this.goal[position])) {
          ++position;
          if (position == this.goal.length) {
            return seed;
          }
          rnd = random.nextInt(27);
        }
        seed += this.step;
      }

      throw new Exception("No match found");
    }
  }

  public static void main(String[] args) {
    final String GOAL = "hello".toLowerCase();
    final int NUM_CORES = Runtime.getRuntime().availableProcessors();

    final ArrayList<SearchTask> tasks = new ArrayList<>(NUM_CORES);
    for (int i = 0; i < NUM_CORES; ++i) {
      tasks.add(new SearchTask(GOAL, i, NUM_CORES));
    }

    final ExecutorService executor = Executors.newFixedThreadPool(NUM_CORES, new ThreadFactory() {

      @Override
      public Thread newThread(Runnable r) {
        final Thread result = new Thread(r);
        result.setPriority(Thread.MIN_PRIORITY); // make sure we do not block more important tasks
        result.setDaemon(false);
        return result;
      }
    });
    try {
      final Long result = executor.invokeAny(tasks);
      System.out.println("Seed for \"" + GOAL + "\" found: " + result);
    } catch (Exception ex) {
      System.err.println("Calculation failed: " + ex);
    } finally {
      executor.shutdownNow();
    }
  }
}

Другие ответы объясняют, почему, но вот как.

Учитывая экземпляр Random :

Random r = new Random(-229985452)

Первые 6 чисел, которые r.nextInt(27) следующие:

8
5
12
12
15
0

и первые 6 чисел, которые r.nextInt(27) заданы Random r = new Random(-147909649) :

23
15
18
12
4
0

Затем просто добавьте эти числа в целочисленное представление символа ` (которое равно 96):

8  + 96 = 104 --> h
5  + 96 = 101 --> e
12 + 96 = 108 --> l
12 + 96 = 108 --> l
15 + 96 = 111 --> o

23 + 96 = 119 --> w
15 + 96 = 111 --> o
18 + 96 = 114 --> r
12 + 96 = 108 --> l
4  + 96 = 100 --> d

Все здесь проделали большую работу по разъяснению того, как работает код, и показывая, как вы можете создавать свои собственные примеры, но вот теоретический ответ информации, показывающий, почему мы можем разумно ожидать, что существует решение, которое в конечном итоге найдет поиск грубой силы.

26 разных строчных букв образуют наш алфавит Σ . Чтобы разрешить генерировать слова различной длины, мы дополнительно добавляем символ терминатора чтобы получить расширенный алфавит Σ' := Σ ∪ {⊥} .

Пусть α - символ, X - равномерно распределенная случайная величина над Σ' . Вероятность получения этого символа P(X = α) и его информационного содержания I(α) определяется следующим образом:

P (X = α) = 1 / | Σ '| = 1/27

I (α) = -log₂ [P (X = α)] = -log₂ (1/27) = log₂ (27)

Для слова ω ∈ Σ* и его ⊥- аналога ω' := ω · ⊥ ∈ (Σ')* , имеем

I (ω): = I (ω ') = | ω' | * log₂ (27) = (| ω | + 1) * log₂ (27)

Поскольку генератор псевдослучайных чисел (PRNG) инициализируется 32-битным семенем, мы можем ожидать, что большинство слов длиной до

λ = пол [32 / log₂ (27)] - 1 = 5

чтобы сгенерировать, по меньшей мере, одно семя. Даже если мы будем искать 6-символьное слово, мы все равно будем добиваться успеха примерно в 41,06% случаев. Не так уж и плохо.

Для 7 букв мы смотрим ближе к 1.52%, но я не осознавал этого, прежде чем дать ему попробовать:

#include <iostream>
#include <random>

int main()
{
    std::mt19937 rng(631647094);
    std::uniform_int_distribution<char> dist('a', 'z' + 1);

    char alpha;
    while ((alpha = dist(rng)) != 'z' + 1)
    {
        std::cout << alpha;
    }
}

Смотрите вывод: http://ideone.com/JRGb3l


Большинство генераторов случайных чисел являются, по сути, «псевдослучайными». Это линейные конгруэнтные генераторы или LCG ( http://en.wikipedia.org/wiki/Linear_congruential_generator )

LCG вполне предсказуемы, учитывая фиксированное семя. В принципе, используйте семя, которое дает вам первую букву, а затем напишите приложение, которое продолжает генерировать следующий int (char), пока вы не нажмете следующую букву в целевой строке и не запишите, сколько раз вам приходилось вызывать LCG. Продолжайте, пока не создадите каждую букву.


Вот небольшое улучшение для answer Дениса Тульского. Это сокращает время наполовину

public static long[] generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();

    int[] dif = new int[input.length - 1];
    for (int i = 1; i < input.length; i++) {
        dif[i - 1] = input[i] - input[i - 1];
    }

    mainLoop:
    for (long seed = start; seed < finish; seed++) {
        Random random = new Random(seed);
        int lastChar = random.nextInt(27);
        int base = input[0] - lastChar;
        for (int d : dif) {
            int nextChar = random.nextInt(27);
            if (nextChar - lastChar != d) {
                continue mainLoop;
            }
            lastChar = nextChar;
        }
        if(random.nextInt(27) == 0){
            return new long[]{seed, base};
        }
    }

    throw new NoSuchElementException("Sorry :/");
}

Принципал - это случайный класс, построенный с одним и тем же семенем, каждый раз генерирует одинаковый шаблон чисел.


(1) Это даст вам все колпачки и номера:

import string, random
passkey=''
for x in range(8):
    if random.choice([1,2]) == 1:
        passkey += passkey.join(random.choice(string.ascii_uppercase))
    else:
        passkey += passkey.join(random.choice(string.digits))
print passkey 

(2) Если позже вы захотите включить строчные буквы в свой ключ, это также будет работать:

import string, random
passkey=''
for x in range(8):
    if random.choice([1,2]) == 1:
        passkey += passkey.join(random.choice(string.ascii_letters))
    else:
        passkey += passkey.join(random.choice(string.digits))
print passkey  






java string random