Равное количество в битах

Discussion in 'WASM.A&O' started by EvilsInterrupt, Apr 29, 2005.

  1. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Blog Posts:
    0
    Я не знал как тему назвать,поэтому назвал так, хоть отдаленно но немного подходящее к задаче котороую мне надо решить.



    Задача заключается в следующем:

    Есть две последоватаельности байтов. Одна из 25 байтов, а другая из 32 байтов.



    Надо составить последовательности так, чтобы биты были равновероятными или хотя бы стремились к этому.



    Пример из двух байтов:

    1010 1010

    0101 0101

    Если взять 7ые биты то количество 0 и 1 одинаково, такоже и в других разрядах.



    Составить последовательности так, что если ты одно значение уже ввел в какую либо последовательность, то более ты уже не имеешь права вводить в ни в первую не во вторую последовательность такой же байт. То есть если в одной последовательности есть уже 4ah, то ни в этой последовательности не в другой такого значение быть не может!



    Вопрос: можно ли составить такую последовательности? Если нет, та какие последовательности, наиболее будут стремиться к этим требованиям?



    Спасибо за внимание
     
  2. RElf

    RElf New Member

    Blog Posts:
    0
    А зачем именно две последовательности длины 25 и 32, а не одна длины 25+32? Равновероятности битов можно добиться каждый раз беря вместе с байтом b его инверсию ~b. Но так как суммарная длина последовательностей нечетна, то точного совпадения количества нулей и единиц получить нельзя - у одного какого-то байта не будет инверсии.
     
  3. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Blog Posts:
    0
    Приведу кусок кода:
    Code (Text):
    1.  
    2.     mov ecx,256d
    3.     mov esi,offset buf
    4.     xor eax,eax
    5. gen_buf:
    6.     mov byte ptr[esi],al
    7.     inc esi
    8.     inc eax
    9.     loop    buf
    10. ...
    11. buf db 256d dup(0)
    12.  


    Если ты заглянешь в отладчик и посмотришь buf, после loop тебе много станет понятно!

    Только не смейся, если че смешного нашел :)))
     
  4. RElf

    RElf New Member

    Blog Posts:
    0


    Можно и не заглядывать. В buf будет последовательность байт от 0 до 0xFF. И как это связано с исходной задачей?
     
  5. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Blog Posts:
    0
    Тогда если ты глянешь на смещения в этом буфер на 41h до скажем 5Ah и с 0с0h до 0dfh ну а далее на аналогичные массивы! ТО именно в этих последовательность мне не нравится статичность, поэтому я хочу сделать свой массив в которых будет куда получше чем в оригинальных массивах!
     
  6. RElf

    RElf New Member

    Blog Posts:
    0




    Борешся со статическим распознаванием текста? Замена тут не сильно поможет так как легко распознается частотным анализом. Почему бы вместо этого, например, просто не зашифровать текст каким-нибудь поточным алгоритмом (например, RC4) на фиксированном ключе. Тогда на выходе будет нечто неотличимое от случайной последовательности байт со всеми хорошими статистическими свойствами.
     
  7. iron_nomad

    iron_nomad New Member

    Blog Posts:
    0
    RElf

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



    С RC4 я не знаком, но посмотрю его.



    Плюс не мог бы ты посоветовать алгоритм в котором можно шифровать только используя ключ шифрования, рса не предлагать - громоздко!
     
  8. The Svin

    The Svin New Member

    Blog Posts:
    0
    Я опять ничего не понял :)

    Нужен алгоритм генерации нового числа с таким же количеством бит как в заданном?
     
  9. RElf

    RElf New Member

    Blog Posts:
    0




    Все алгоритмы асимметричной криптографии так или иначе "громозки". В качестве альтернатывы RSA можно посмотреть на ElGamal и NTRU.
     
  10. iron_nomad

    iron_nomad New Member

    Blog Posts:
    0
    >нового числа

    Последовательности, а речь идет о том чтобы убрать частотность битов в кодировке win-1258. К примеру если ты составишь массив по коду выше, то увидишь, что по смещению 41h и так до Z стоит лат.алфавит загланых букв у них у каждой буквы 6й бит равен "1"
     
  11. flankerx

    flankerx New Member

    Blog Posts:
    0


    а если поверх нормальный алгоритм -- то нафига ты вообще этот огород городишь?



    Честно говоря, я не вижу особой связи между исходной постановкой задачи и тем, что тут обсуждается :dntknw:





    На это сеществуют генераторы псевдослучайных последовательностей. Тот же RC4, например. Любой блочный шифр в режиме CTR. И многое другое.
     
  12. iron_nomad

    iron_nomad New Member

    Blog Posts:
    0
    Code (Text):
    1.  
    2. 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F  @ABCDEFGHIJKLMNO
    3.  


    Это кусок из дампа. Если теперь это посмотреть как на биты, то:
    Code (Text):
    1.  
    2. 0100 0001
    3. 0100 0010
    4. 0100 0011
    5. 0100 0100
    6. 0100 0101
    7. 0100 0110
    8. 0100 0111
    9. 0100 1000
    10. 0100 1001
    11. 0100 1010
    12. 0100 1011
    13. 0100 1100
    14. 0100 1101
    15. 0100 1110
    16. 0100 1111


    Ка видно каждая "буква" лат.алфавита прописных букв содержит в 6м

    бите "1" и в 5м "0". В строчных буквах тоже есть статичность. В

    русском алфавите тоже есть, как в заглавных так и в строчных. Мне

    нужно избавиться от этой статичности! Для этого я подумал об новой

    кодировке, которая бы убирала эту статичность.



    Критерии бы к кодировке были бы таковы:

    1. Каждый байт уникален, иначе это не кодировка

    2. Если смотреть на биты последовательности, скажем лат. заглавные,

    то в этой последовательности биты должны стремиться к равновероят-

    ности, Т.е. если расположить байты, как я расположил выше, то в 7м

    бите должно быть одинаковое кол-во "1" и "0", и в 6м, и в 5м, и в 4м,

    и так далее...



    Или максимально стремиться к этому!



    Я предполагаю что из-за того, что каждый байт должен быть уникален,

    то 2й критерий полностью неможет выполниться, более того, у меня

    чувство, что одна последовательность будет более соответствовать 2му

    критерею чем другая, а я бы не хотел такого. Лучше бы одинаково

    распредилить статичность, как на заглавные и строчные любого алфавита.
     
  13. flankerx

    flankerx New Member

    Blog Posts:
    0
    ну а в чем проблема?

    выпиши все свои abcd...xyz и под ними напиши _случайные_ байты (из любого нормального ГПСЧ). Или вообще возьми base32/base64.



    а вообще ИМХО то что ты делаешь -- это глупость (или я чего-то не понимаю). Избыточность содержится не в способе кодировки -- она в самом языке.
     
  14. iron_nomad

    iron_nomad New Member

    Blog Posts:
    0
    flankerx



    То что в языке это я знаю, но когда избыточность убрана из битов это уже получше.
     
  15. iron_nomad

    iron_nomad New Member

    Blog Posts:
    0
    flankerx

    и еще спасибо, за подсказку, но я так и делал, но на человеческие мозги в генерации хороших последовательность лучше не полагаться
     
  16. valterg

    valterg Active Member

    Blog Posts:
    0
    EvilsInterrupt

    На выбор два алгоритма.

    1) Не учитываем избыточность : просто генерим случайные последовательности из 8 бит, проверяя на "повторы".

    2) С учетом избыточности : код Huffman-a - часто встречающиеся буквы будут кодироваться меньшим числом бит и равновероятнось 0/1 идеальна с учетом дискретности материала. Для достижения более идеальной равновероятности у того же Huffmana предлагается кодировать пары и тройки букв и т.д до слов.

    +++++++++++++++++++++

    А собственно любой алгоритм сжатия и выдаст равновероятный поток битов.
     
  17. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Blog Posts:
    0
    valterg



    Интересных тебе багов! старший товарищ. :)))
     
  18. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Blog Posts:
    0