После написания заметки о генераторах фракталов , меня посетила одна идея. В свое время я интересовался автоматическим распознаванием капч (которые captcha). Так вот, распознавание происходит в несколько этапов. Текст капчи отделяются от фона, вычищается от мусора, нарезается на буквы. Затем буквы приводятся к одному размеру и используются для обучения нейронной сети . Притом первый шаг — отделение текста от фона, как правило, является довольно простым.
Давайте посмотрим на некоторые капчи:
Обратите внимание на номера с 4-го по 7-й. Эти капчи достаточно контрастны для того, чтобы преобразовать их в черно-белое изображение (матрицу ноликов и единичек) практически без потери информации. С капчей номер 3 та же проблема, хотя это и менее очевидно. На самом деле она даже слабее остальных капч, потому что позволяет легко разбить изображенное число на цифры.
Вы могли узнать капчу номер 1, она использовалась (до сих пор используется?) Яндексом. И она была успешно взломана без особой магии. Капча номер 2 может показаться надежной, но на самом деле она таковой не является . Капча номер 6 также была взломана .
Номера 4 и 5 — это KCaptcha и Blogger.com соответственно. Обе пока что держатся, видимо за счет сложности нарезания букв. KCaptcha, если вдруг кто не в курсе, пользуется большой популярностью. Например, она используется в движке DLE и на rutracker.org.
Однако вернемся к упомянутой в начале заметки идее. Она заключается в том, что капчу можно улучшить, залатав одно из ее уязвимых мест, а именно — усложнить отделение текста от фона. Зачем выводить текст каким-то одним цветом на белом или любом другом фоне, если можно сделать фон и цвет текста постоянно меняющимися?
При чем тут фракталы? Как выяснилось, есть такой алгоритм генерации красивых картинок под названием плазма . Алгоритм очень простой. И да, картинка, которую он выдает на выходе — это тоже фрактал.
Иллюстрация к предыдущим двум абзацам:
Остается доработать кое-какие мелочи (менять смещение, наклон и размер цифр, применить пару фильтров), но идею, надеюсь, вы поняли. Такая капча, конечно, не очень привлекательна в плане юзабилити. Но когда речь заходит о безопасности, всегда приходится искать компромисс.
Плавно переходим от теории к практике. Реализовывал я все это хозяйство на Python . Вот, что получилось:
# -*- coding: utf-8 -*-
# FractalCaptcha.py v 0.1
# (c) Alexandr A Alexeev 2011 | http://remontka.com/
from PIL import Image , ImageDraw , ImageFont , ImageFilter
from random import random
# создаем капчу, содержащую символы из строки secret
def captcha ( secret , width = 200 , height = 80 ,
fontName = ‘arial.ttf’ , fontSize = 54 ,
blur = 2 ) :
mask = Image. new ( ‘RGBA’ , ( width , height ) )
font = ImageFont. truetype ( fontName , fontSize )
x_offset = — 10
draw = ImageDraw. Draw ( mask )
for i in range ( len ( secret ) ) :
x_offset + = 20 + int ( random ( ) * 20 )
y_offset = — 10 + int ( random ( ) * 30 )
draw. text ( ( x_offset , y_offset ) , secret [ i ] , font = font )
# последний символ также должен быть повернут
angle = — 10 + int ( random ( ) * 15 )
mask = mask. rotate ( angle )
bg = plazma ( width , height )
fg = plazma ( width , height )
result = Image. composite ( bg , fg , mask )
# blur усложнит выделение границ символов
# альтернативный вариант — гаусово размытие:
# http://rcjp.wordpress.com/2008/04/02/gaussian-pil-image-filter/
if blur > 0 :
for i in range ( blur ) :
result = result. filter ( ImageFilter. BLUR )
# почему-то blur иногда не действует на границах капчи
# использовать crop?
return result
# генерируем «плазму» размером width x height
def plazma ( width , height ) :
img = Image. new ( ‘RGB’ , ( width , height ) )
pix = img. load ( ) ;
for xy in [ ( 0 , 0 ) , ( width- 1 , 0 ) , ( 0 , height- 1 ) , ( width- 1 , height- 1 ) ] :
rgb = [ ]
for i in range ( 3 ) :
rgb. append ( int ( random ( ) * 256 ) )
pix [ xy [ 0 ] , xy [ 1 ] ] = ( rgb [ 0 ] , rgb [ 1 ] , rgb [ 2 ] )
plazmaRec ( pix , 0 , 0 , width- 1 , height- 1 )
return img
# рекурсивная составляющая функции plazma
def plazmaRec ( pix , x1 , y1 , x2 , y2 ) :
if ( abs ( x1 — x2 ) <= 1 ) and ( abs ( y1 — y2 ) <= 1 ) :
return
rgb = [ ]
for i in range ( 3 ) :
rgb. append ( ( pix [ x1 , y1 ] [ i ] + pix [ x1 , y2 ] [ i ] ) / 2 )
rgb. append ( ( pix [ x2 , y1 ] [ i ] + pix [ x2 , y2 ] [ i ] ) / 2 )
rgb. append ( ( pix [ x1 , y1 ] [ i ] + pix [ x2 , y1 ] [ i ] ) / 2 )
rgb. append ( ( pix [ x1 , y2 ] [ i ] + pix [ x2 , y2 ] [ i ] ) / 2 )
tmp = ( pix [ x1 , y1 ] [ i ] + pix [ x1 , y2 ] [ i ] +
pix [ x2 , y1 ] [ i ] + pix [ x2 , y2 ] [ i ] ) / 4
diagonal = ( ( x1-x2 ) ** 2 + ( y1-y2 ) ** 2 ) ** 0.5
while True :
delta = int ( ( ( random ( ) — 0.5 ) / 100 * min ( 100 , diagonal ) ) * 255 )
if ( tmp + delta >= 0 ) and ( tmp + delta <= 255 ) :
tmp + = delta
break
rgb. append ( tmp )
pix [ x1 , ( y1 + y2 ) / 2 ] = ( rgb [ 0 ] , rgb [ 5 ] , rgb [ 10 ] )
pix [ x2 , ( y1 + y2 ) / 2 ] = ( rgb [ 1 ] , rgb [ 6 ] , rgb [ 11 ] )
pix [ ( x1 + x2 ) / 2 , y1 ] = ( rgb [ 2 ] , rgb [ 7 ] , rgb [ 12 ] )
pix [ ( x1 + x2 ) / 2 , y2 ] = ( rgb [ 3 ] , rgb [ 8 ] , rgb [ 13 ] )
pix [ ( x1 + x2 ) / 2 , ( y1 + y2 ) / 2 ] = ( rgb [ 4 ] , rgb [ 9 ] , rgb [ 14 ] )
plazmaRec ( pix , x1 , y1 , ( x1+x2 ) / 2 , ( y1+y2 ) / 2 )
plazmaRec ( pix , ( x1+x2 ) / 2 , y1 , x2 , ( y1+y2 ) / 2 )
plazmaRec ( pix , x1 , ( y1+y2 ) / 2 , ( x1+x2 ) / 2 , y2 )
plazmaRec ( pix , ( x1+x2 ) / 2 , ( y1+y2 ) / 2 , x2 , y2 )
if __name__ == ‘__main__’ :
result = captcha ( «12345» )
result. save ( «result.png» , «PNG» )
Если под Windows интерпретатор будет ругаться по поводу поддержки шрифтов, поставьте PIL отсюда . Капча будет смотреться красивее, если использовать шрифт Comic Sans MS.
Важный момент. Перед тем, как вернуть картинку, мы пару раз применяем к ней фильтр blur. Если этого не делать, будет относительно несложно выделить контуры символов. Я рисовал капчи в Gimp в соответствии с последней иллюстрацией, делал различные варианты размытия, а затем пытался выделить границы символов с помощью фильтров типа «Лаплас», «Неон» и их комбинаций. Выяснилось, что лучше всего границы скрываются либо после многократного размытия изображения по Гауссу, либо после многократного blur.
Поскольку в PIL нет размытия по Гауссу, выбор пришлось сделать в пользу blur. С другой стороны, а что нам мешает использовать стороннюю реализацию размытия по Гауссу? Вот соответствующая заплатка к скрипту:
> from numpy import mgrid, exp
>
> def gaussian_grid(size = 5):
> m = size/2
> n = m+1 # remember python is ‘upto’ n in the range below
> x, y = mgrid[-m:n,-m:n]
> fac = exp(m**2)
> g = fac*exp(-0.5*(x**2 + y**2))
> return g.round().astype(int)
>
> class GAUSSIAN(ImageFilter.BuiltinFilter):
> name = «Gaussian»
> gg = gaussian_grid().flatten().tolist()
> filterargs = (5,5), sum(gg), 0, tuple(gg)
32,34d45
< # blur усложнит выделение границ символов
< # альтернативный вариант — гаусово размытие:
< # http://rcjp.wordpress.com/2008/04/02/gaussian-pil-image-filter/
37,38c48
< result = result.filter(ImageFilter.BLUR)
<
—
> result = result.filter(GAUSSIAN)
Число применений фильтра передается функции создания капчи в качестве аргумента, так что вы легко сможете найти компромисс между безопасностью и юзабилити. Примеры капч:
В этой заметке я хотел продемонстрировать лишь идею . Тем не менее, такая реализация капчи кажется мне надежной. Буду рад, если кто-нибудь продемонстрирует обратное. Обратите внимание, что любая графическая капча легко ломается с помощью Anti-Captcha . Для защиты от подобных сервисов нужны дополнительные ухищрения.