Skip to main content
STEM:Hub

Парольная безопасность

  • Содержание: цели политик, сила паролей, алфавиты, длина, почему «маски»/регексы в заданиях — модель политики.

  • Навыки: распознавание плохих правил (например, «минимум одна заглавная» при общей длине 6 — слабое требование).

  • Практика: оценить «силу» нескольких политик и сравнить их.

  • Мы описываем политику пароля как множество допустимых строк.

  • Регулярные выражения — формальная модель этой политики.

  • В задачах важна строгость: указываем алфавит явно, якорим шаблоны ^…$.

Предварительные знания

  • Комбинаторика: произведение мощностей множеств; степени; альтернативы.
  • Интуитивное понимание энтропии:
\(H \approx n \cdot \log_2 |\Sigma|\)
  • ASCII vs Unicode: латиница/кириллица — разные кодовые точки, «похожие» символы — не одно и то же.
  1. Ключевые понятия

  • Политика паролей = формальные правила допустимых строк (алфавит, длина, обязательные классы символов, запреты). Это не про «какой пароль выберет человек», а про множество разрешённых паролей.

  • Сила политики (теоретическая) ≈ размер пространства паролей. При равновероятном выборе:

\(H \approx n \cdot \log_2(|\Sigma|) \text{ бит}, \quad \text{где } n \text{ — длина}, |\Sigma| \text{ — мощность алфавита}.\)

  • log2(10) ≈ 3.322, log2(26) ≈ 4.700, log2(52) ≈ 5.700, log2(62) ≈ 5.954, log2(95) ≈ 6.570.

  • Сила пароля (практическая) зависит от модели атакующего и распределений (человеческий выбор, словари, лики). На олимпиадах чаще оцениваем силу политики.

  • Длина почти всегда сильнее «добавления классов». Один дополнительный символ при |Σ|=62 даёт ≈6 бит; чтобы получить столько же за счёт расширения алфавита, его пришлось бы умножить примерно на 2^6 ≈ 64.

  1. Алфавиты, длина, классы
  • Примеры алфавитов:
    • Только цифры: |Σ|=10
    • Лат. строчные: 26; лат. буквы (стр+пр): 52; буквы+цифры: 62; печатные ASCII ~95
  • Unicode-нюанс: чётко фиксируйте, что входит в классы (ASCII-латиница vs все буквы Unicode). «Похожие» символы (о vs о) — не одно и то же.
  • «Хотя бы по одному символу из класса» уменьшает пространство по сравнению с «любые из объединённого алфавита». Для грубой верхней оценки иногда берут |Σ|^n; для точного счёта — включение-исключение (будет в модуле 5).
  1. Почему маски/регексы = модель политики
  • Маска/регекс — точное описание множества допустимых строк, т.е. формализация политики.
  • Примеры:
    • «Только латиница и цифры, длина 8–12»: ^[A-Za-z0-9]{8,12}$
    • «≥1 заглавная и ≥1 цифра, длина ≥6»:
      • Модель: (?=.[A-Z])(?=.\d)[A-Za-z0-9]{6,}$
    • На олимпиадах встречаются «самодельные маски» с переопределёнными символами — их переводим в стандартный регекс (подробно в модуле 4).
  1. Распознаём слабые правила
  • Малая минимальная длина: «≥6 символов» почти всегда слабо, даже при «хотя бы один из…».
  • Обязательные классы без увеличения длины: «добавьте цифру» даёт немного бит; длина решает больше.
  • Размытые алфавиты: «буквы» без уточнения про алфавит/Unicode.
  • Предсказуемые шаблоны (человеческий фактор): «Первая — заглавная, дальше строчные и в конце цифра» — формально допустимо, фактически легко угадывается.
  • Отсутствие якорей в регексе: без ^ и $ правило проверяет подстроку, а не весь пароль.
  1. Быстрые численные ориентиры (нижние/верхние оценки)
  • 6 символов, буквы+цифры (62): ≈ 6 · 5.95 ≈ 35.7 бит (верхняя оценка; с «≥1 заглавной и ≥1 цифры» будет чуть меньше).
  • 8 символов, 62-алфавит: ≈ 47.6 бит.
  • 10 символов, только цифры: ≈ 33.2 бит.
  • 12 символов, только строчные (26): ≈ 12 · 4.70 ≈ 56.4 бит. Вывод: «только цифры, длина 10» слабее, чем «буквы+цифры, длина 8»; «строчные, длина 12» сильнее обоих.
  1. Мини-практика (сразу потренируемся) Оцените силу минимально допустимых паролей по политикам (дайте порядок от слабой к сильной и прикиньте биты):
  • A: длина ≥6; ≥1 заглавная, ≥1 цифра; алфавит [A-Za-z0-9].
  • B: длина ≥8; алфавит [A-Za-z0-9].
  • C: длина =10; алфавит [0-9].
  • D: длина ≥12; алфавит [a-z]. Подсказка: используйте H ≈ n·log2(|Σ|) как верхнюю оценку; у A учтите, что реальные мощности чуть ниже из-за ограничений «хотя бы по одному».
  1. Чек-лист для оценки политики
  • Ясно ли определён алфавит? (ASCII vs Unicode, исключения)
  • Достаточна ли минимальная длина? (целитесь ≥10–12 для соревновательных задач без доп. факторов)
  • Нет ли «слабых шаблонов», подталкивающих к предсказуемости?
  • Полное соответствие строки? (якоря ^$)
  • Понимаете ли, как правило отразить маской/регексом и как посчитать мощность множества?

Ниже — разбор мини-политик A–D: аккуратные регексы (с якорями и ASCII-ограничением) и оценка “силы” через размер пространства. Для A предоставлена точная формула включения–исключения.

Обозначения:

  • Алфавиты: |[0-9]|=10, |[a-z]|=26, |[A-Za-z]|=52, |[A-Za-z0-9]|=62.
  • Верхняя оценка энтропии: H ≈ n·log2(|Σ|).
  • Для A (классы “хотя бы по одному”) точное число на длине n: 62^n − 36^n − 52^n + 26^n.

Политика A

  • Условие: длина ≥6; ≥1 заглавная [A-Z], ≥1 цифра [0-9]; алфавит [A-Za-z0-9].
  • Регекс (ASCII-строго, избегаем \d и \w):
    • PCRE/JS/etc.: ^(?=.[A-Z])(?=.[0-9])[A-Za-z0-9]{6,}$
    • Python (рекомендация): re.fullmatch с шаблоном (?=^[A-Za-z0-9]{6,}$)(?=.[A-Z])(?=.[0-9]).* и флагом re.ASCII, либо как в строке выше и отдельно проверять fullmatch.
  • Подсчет (для минимальной длины 6):
    • Точно: N = 62^6 − 36^6 − 52^6 + 26^6.
    • Доля от 62^6: p ≈ 1 − (36/62)^6 − (52/62)^6 + (26/62)^6 ≈ 0.619.
    • Энтропия: log2(N) ≈ 35.0 бит (на ~0.7 бита меньше, чем 62^6 без ограничений).
  • Для длины n (ровно n): N(n) = 62^n − 36^n − 52^n + 26^n.

Политика B

  • Условие: длина ≥8; алфавит [A-Za-z0-9].
  • Регекс: ^[A-Za-z0-9]{8,}$
  • Оценка (по минимальной длине 8): N ≈ 62^8, H ≈ 8·log2(62) ≈ 47.6 бита.

Политика C

  • Условие: длина =10; алфавит [0-9].
  • Регекс (строго ASCII-цифры, без \d): ^[0-9]{10}$
  • Подсчет: N = 10^10, H ≈ 10·log2(10) ≈ 33.2 бита.

Политика D

  • Условие: длина ≥12; алфавит [a-z] (только строчные латинские, без Unicode).
  • Регекс: ^[a-z]{12,}$ (включите ASCII-режим при необходимости, и не используйте флаг i)
  • Оценка (по минимальной длине 12): N ≈ 26^12, H ≈ 12·log2(26) ≈ 56.4 бита.

Итог (по минимально допустимой длине):

  • Слабее → сильнее: C (≈33.2 б) < A (≈35.0 б) < B (≈47.6 б) < D (≈56.4 б).

Замечания точности и практики

  • Всегда якорьте правила: ^…$ — иначе проверяется подстрока.
  • Не используйте \w и \d без осознания Unicode-семантики: \d может матчить небуквальные ASCII-цифры, \w включает “_” и буквы из Unicode.
  • Для строгой ASCII-семантики: используйте явные диапазоны и/или флаги (re.ASCII в Python, укажите u-не включать или соответствующие опции в движке).