Could you write what are positions of missing characters? At the end, at the beginning, in the middle? Is it one group or there are several groups?

If it is one group and as you seem to have public key (is it indeed correct?), it should be doable with Kangaroo in a very reasonable time.